Nicolas Bousquet
email: nicolas.bousquet@grenoble-inp.fr

Marc Heinrich

A polynomial version of Cereceda's conjecture *

Let k and d be such that k ≥ d + 2. Consider two k-colourings of a d-degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length.

The k-reconfiguration graph of G is the graph whose vertices are the proper k-colourings of G, with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the (d + 2)-reconfiguration graph of any d-degenerate graph on n vertices is O(n 2 ). So far, the existence of a polynomial diameter is open even for d = 2.

In this paper, we prove that the diameter of the k-reconfiguration graph of a d-degenerate graph is O(n d+1 ) for k ≥ d + 2. Moreover, we prove that if k ≥ 3 2 (d + 1) then the diameter of the k-reconfiguration graph is quadratic, improving the previous bound of k ≥ 2d + 1. We also show that the 5-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs.

Introduction

Reconfiguration problems consist in finding step-by-step transformations between two feasible solutions of a problem such that all intermediate states are also feasible. Such problems model dynamic situations where a given solution already in place has to be modified for a more desirable one while maintaining some properties all along the transformation. Reconfiguration problems have been studied in various fields such as discrete geometry [START_REF] Bose | Flipping edge-labelled triangulations[END_REF], optimization [START_REF] Böckenhauer | Reoptimization of Parameterized Problems[END_REF] or statistical physics [START_REF] Mohar | On the non-ergodicity of the Swendsen-Wang-Kotecký algorithm on the Kagomé lattice[END_REF]. For a complete overview of the reconfiguration field, the reader is referred to the two recent surveys on the topic [START_REF] Nishimura | Introduction to reconfiguration[END_REF][START_REF] Van Den | The Complexity of change[END_REF]. In this paper, our reference problem is graph colouring.

Let Π be a problem and I be an instance of Π. The reconfiguration graph is the graph where vertices are solutions of I and where there is an edge between two vertices if one can transform the first solution into the other in one step (for graph colouring one step means modifying the colour of a single vertex 1 ). Given a reconfiguration problem, several questions may arise. (i) Is it possible to transform any solution into any other, i.e. is the reconfiguration graph connected? (ii) If yes, how many steps are needed to perform this transformation, i.e. what is the diameter of the reconfiguration graph? In this work, we will focus on the diameter of the reconfiguration graph. The diameter of the reconfiguration graph plays an important role, for instance in random sampling, since it provides a lower bound on the mixing time of the underlying Markov chain (and the connectivity of the reconfiguration graph ensures the ergodicity of the Markov chain2 ). Since proper colourings correspond to states of the antiferromagnetic Potts model at zero temperature, Markov chains related to graph colourings received a considerable attention in statistical physics and many questions related to the ergodicity or the mixing time of these chains remain widely open (see e.g. [START_REF] Chen | Improved bounds for randomly sampling colorings via linear programming[END_REF][START_REF] Frieze | A survey on the use of markov chains to randomly sample colourings[END_REF]).

Graph recolouring. All along the paper G = (V, E) denotes a graph, n is the size of V and k is an integer. For standard definitions and notations on graphs, we refer the reader to [START_REF] Diestel | Graph Theory[END_REF]. A (proper) k-colouring of G is a function f : V (G) → {1, . . . , k} such that, for every edge xy ∈ E, we have f (x) = f (y). Throughout the paper we will only consider proper colourings and will then omit the proper for brevity. The chromatic number χ(G) of a graph G is the smallest k such that G admits a k-colouring. Two k-colourings are adjacent if they differ on exactly one vertex. The k-reconfiguration graph of G, denoted by G(G, k) and defined for any k ≥ χ(G), is the graph whose vertices are k-colourings of G, with the adjacency relation defined above. Cereceda, van den Heuvel and Johnson provided an algorithm to decide whether, given two 3-colourings, one can be transformed into the other in polynomial time, and characterized graphs for which G(G, 3) is connected [START_REF] Cereceda | Mixing 3-colourings in bipartite graphs[END_REF][START_REF] Cereceda | Finding paths between 3-colorings[END_REF]. Given any two k-colourings of G, it is PSPACE-complete to decide whether one can be transformed into the other for k ≥ 4 [START_REF] Bonsma | Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances[END_REF].

The

k-recolouring diameter of a graph G is the diameter of G(G, k) if G(G, k
) is connected and is equal to +∞ otherwise. In other words, it is the minimum D for which any k-colouring can be transformed into any other one through a sequence of at most D adjacent k-colourings. Bonsma and Cereceda [START_REF] Bonsma | Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances[END_REF] proved that there exists a family G of graphs and an integer k such that, for every graph G ∈ G there exist two k-colourings whose distance in the k-reconfiguration graph is finite and super-polynomial in n.

Cereceda conjectured that the situation is different for degenerate graphs. A graph G is ddegenerate if any subgraph of G admits a vertex of degree at most d. In other words, there exists an ordering v 1 , . . . , v n of the vertices such that for every i ≤ n, the vertex v i has at most d neighbours in v i+1 , . . . , v n . It was shown independently by Dyer et al. [START_REF] Dyer | Randomly coloring sparse random graphs with fewer colors than the maximum degree[END_REF] and by Cereceda et al. [START_REF] Cereceda | Mixing 3-colourings in bipartite graphs[END_REF] that for any d-degenerate graph G and every k ≥ d + 2, G(G, k) is connected. However the (upper) bound on the k-recolouring diameter given by these constructive proofs is of order c n (where c is a constant). Cereceda [START_REF] Cereceda | Mixing Graph Colourings[END_REF] conjectured that the the diameter of G(G, k) is of order O(n 2 ) as long as k ≥ d + 2. If correct, the quadratic function is sharp, even for paths or chordal graphs as proved in [START_REF] Bonamy | Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF]. The existence of a polynomial upper bound instead of a quadratic one also is open, even for d = 2 or restricted to particular graph classes such as planar graphs. In what follows, we will call respectively the polynomial (resp. quadratic) Cereceda's conjecture the question of proving that the k-recolouring diameter of d-degenerate graphs is polynomial (resp. quadratic) for k ≥ d + 2.

The quadratic Cereceda's conjecture is known to be true only for d = 1 (for trees) [START_REF] Bonamy | Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF] and d = 2 with ∆ ≤ 3 [START_REF] Feghali | A reconfigurations analogue of brooks' theorem and its consequences[END_REF] (where ∆ denotes the maximum degree of the graph). Cereceda [START_REF] Cereceda | Mixing Graph Colourings[END_REF] showed that k-recoloring diameter Lower bound Upper bound

k = d + 2 O(n 2 ) [5] O(n d+1 ) [Theorem 1] k = d + 3 O(n) O(n d+1 2 ) [Theorem 1] k ≥ (1 + ε)(d + 1) O(n) O(n 1/ε ) [Theorem 1] k ≥ 3 2 (d + 1) O(n) O(n 2 ) [Theorem 1] k ≥ 2(d + 1) O(n) O(n) [8]
Figure 1: Known results on the k-recolouring diameter of d-degenerate graphs.

for any d-degenerate graph G and every

k ≥ 2d + 1, the diameter of G(G, k) is O(n 2
). Bousquet and Perarnau proved that when k ≥ 2d + 2, the diameter of G(G, k) is linear [START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF].

Even if the conjecture is open for general graphs, it has been proved for several graph classes such as chordal graphs [START_REF] Bonamy | Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF] and bounded treewidth graphs [START_REF] Bonamy | Recoloring graphs via tree decompositions[END_REF]. The polynomial Cereceda's conjecture holds if we replace degeneracy by maximum average degree [START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF][START_REF] Feghali | Paths between colourings of sparse graphs[END_REF]. In particular, it implies that the 8-recolouring diameter of a planar graph is polynomial. The polynomial Cereceda's conjecture asks for more since it states that the diameter should be polynomial when k = 7. So far, the best known upper bound on the 7-recolouring diameter of planar graphs was subexponential [START_REF] Eiben | Towards cereceda's conjecture for planar graphs[END_REF].

Our result. The main result of the paper is the following: Theorem 1. Let d, k ∈ N and G be a d-degenerate graph. Then G(G, k) has diameter at most:

• Cn 2 if k ≥ 3 2 (d + 1
) (where C is a constant independent of k and d),

• C ε n 1/ε if k ≥ (1 + ε)(d + 2
) and 0 < ε < 1 (where C ε is a constant independent from k and d),

• (Cn) d+1 for any d and k ≥ d + 2 (where C is a constant independent from k and d).

In particular, it implies that the 7-recolouring diameter of planar graphs is polynomial (of order O(n 6 )), answering a question of [START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF][START_REF] Feghali | Paths between colourings of sparse graphs[END_REF], and is quadratic if k ≥ 9 (improving the recent result of Feghali giving k ≥ 10 [START_REF] Feghali | Reconfiguring 10-colourings of planar graphs[END_REF]). For general graphs, our result guarantees moreover that the diameter becomes a polynomial independent of d as long as k ≥ (1 + ε)(d + 2). We also obtain a quadratic diameter when the number of colours is at least 3 2 • (d + 1), improving the result of Cereceda [START_REF] Cereceda | Mixing Graph Colourings[END_REF] who obtained a similar result for k ≥ 2d + 1. Note moreover that Theorem 1 ensures that the diameter is polynomial as long as d is a fixed constant, which was open even for d = 2 (we get a diameter of order O(n 3 ) for d = 2). The main known results on lower and upper bounds on the k-recolouring diameter are summarized in Figure 1.

In order to show Theorem 1, we need to prove a more general result that also holds for listcolourings. Indeed, we often need to consider induced subgraphs of our initial graph where the colours of some vertices are"frozen" (i.e. do not change). By considering the list colouring version, we can delete these vertices and remove their colours from the list of all their neighbours. This more general statement implying Theorem 1 is given in Section 2.

We complete Theorem 1 by proving the quadratic Cereceda's conjecture for planar bipartite graphs. Euler's formula ensures that planar bipartite graphs are 3-degenerate. We prove the following in Section 3.

Theorem 2. Let G be a planar bipartite graph. The diameter of G(G, 5) is at most 4n 2 .

Our proof is based on a discharging argument. It is, as far as we know, the first time such a method is used for reconfiguration.

The proofs of both Theorem 1 and Theorem 2 consist in showing that, given two colourings α and β of G, there exists a transformation from α to β of the corresponding length. Since our proofs are algorithmic, they also provide polynomial time algorithms that, given two colourings α and β, output a transformation from α to β of length at most the diameter of the reconfiguration graph.

Further work and open problems. Even if we obtain a polynomial bound on the diameter of the reconfiguration graph, the quadratic conjecture of Cereceda is still open, even for simple classes of graphs such as (triangle-free) planar graphs or 2-degenerate graphs.

Conjecture 3 (Cereceda [START_REF] Cereceda | Mixing Graph Colourings[END_REF]). For every d, there exists

C d such that for every d-degenerate graph G, the diameter of G(G, k) is at most C d • n 2 as long as k ≥ d + 2.
The question of Cereceda in [START_REF] Cereceda | Mixing Graph Colourings[END_REF] is the following "For a graph G with n vertices and k ≥ d + 2 where d is the degeneracy of G, the diameter of G(G, k) is O(n 2 )". We were not be able to determine if the coefficient in front of n 2 has to be a function of d or not. As a consequence we decided to state the weaker possible version of the conjecture. Note that the constants of Theorem 2, for chordal graphs [START_REF] Bonamy | Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF], and for bounded treewidth graphs [START_REF] Bonamy | Recoloring graphs via tree decompositions[END_REF] do not depend on d. A stronger conjecture would then be the following: Question 4 (Stronger Conjecture). There exists a constant C such that, for every d and every

d-degenerate graph G the diameter of G(G, k) is at most C • n 2 as long as k ≥ d + 2.
Another interesting question is the following: what is the evolution of the diameter when the number of colours increases. With our proof technique, the power in the exponent decreases little by little and finally becomes quadratic when the number of colours is at least 3 2 • (d + 1). Improving the factor 3 2 may be another interesting way of tackling the general conjecture. We also know that the diameter becomes linear when k ≥ 2d + 2 [START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF]. Is it possible to improve this result? In particular, can we improve the k-recolouring diameter for 3 2 (d + 1) ≤ k ≤ 2d + 1?

Question 5. Is there α < 2 and β ∈ N such that, for every d and every

d-degenerate graph G the diameter of G(G, k) is at most C d • n when k ≥ αd + β.
It was also proved in [START_REF] Bonamy | Recoloring graphs via tree decompositions[END_REF] that the diameter becomes linear if k is at least the grundy number plus 1, which in particular implies a linear diameter when k ≥ ∆ + 2. When k = ∆ + 1, Feghali, Jonhson and Paulusma [START_REF] Feghali | A reconfigurations analogue of brooks' theorem and its consequences[END_REF] proved that the k-recolouring graph is composed of isolated vertices plus a unique component of diameter at most O(n 2 ) (and this non-isolated component of G(G, ∆ + 1) is exponentially larger than its number of isolated vertices [START_REF] Bonamy | Frozen (∆ + 1)-colourings of bounded degree graphs[END_REF]).

One can also notice in Figure 1 that, as long as k ≥ d+3, no non-trivial lower bound is known on the diameter of the reconfiguration graph. The subtle quadratic lower bound of [START_REF] Bonamy | Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF] when k = d + 2 seems to be hard to adapt if k ≥ d + 3. Developing new techniques to find lower bounds on the k-recolouring diameter of a graph is a challenging open problem.

Polynomial Cereceda's conjecture

Let G be a d-degenerate graph and let v 1 , . . . , v n be a degeneracy ordering. We denote by d + (v) the out-neighbours of v (i.e., neighbours of v which appear later in the ordering). Recall that a graph is d-degenerate if there is a degeneracy ordering such that d + (v) ≤ d for every vertex v of the graph.

Let us first briefly discuss the main ideas of the proof before stating formally all the results. The main idea is to proceed recursively on the degeneracy. More precisely, we want to delete a subset of vertices in order to decrease by one both the degeneracy and the number of colours. In order to do this, observe that if at some point there is one colour c such that every vertex of the graph is either coloured c or has an out-neighbour coloured c, then by removing all the vertices coloured c, we decrease the number of available colours by 1, but we also decrease the degeneracy of the graph by 1. If H is the resulting graph, by applying induction, we can recolour H however we want, and for example, we can remove completely one colour which we can then use to make the two colourings agree on a subset of vertices. If the colour c satisfies the condition above, we will say that the colour c is full. Our main objective will consist in finding a transformation from any colouring α of G to some colouring α of G which has a full colour (Note that any graph can have such a colouring, for example by applying the First-Fit algorithm in the reverse order of the elimination ordering). We will build the colouring α (and the transformation) incrementally. However in order to do this, we will need to generalise the problem to list colouring.

A list assignment L is a function which associates a list of colours to every vertex v. An Lcolouring is a (proper) colouring α of G such that for every vertex v, α(v) ∈ L(v). The total number of colours used by the assignment is

k = | v∈G L(v)|. A list assignment L is a-feasible if |L(v)| ≥ |d + (v)| + a + 1 for every vertex v ∈ G. We just say that it is feasible if it is 1-feasible.
We denote by G(G, L) the reconfiguration graph of the L-colourings of G. (One can easily prove by induction, that if a list assignment is a-feasible for a ≥ 1, then G(G, L) is connected). We will prove a generalisation of Theorem 1 in the case of list colourings. Namely, we will prove that: Theorem 6. Let G be a graph and a ∈ N. Let L be an a-feasible list assignment and k be the total number of colours. Then G(G, L) has diameter at most:

• kn if k ≤ 2a. • Cn 2 if k ≤ 3a (C a constant independent of k, a), • C ε n 1/ε if k ≤ (1 + 1 ε )a where ε is a constant and C ε is independent of k, a, • (Cn) k-1 , if a ≥ 1.
The proof of Theorem 1 follows easily from this result. The only point that is not immediate is that the last point of Theorem 6 implies the last point of Theorem 1. In this case, we need a small trick to guarantee that the diameter does not increase if the number of colours increases. Note that the first point of Theorem 6 implies in terms of classical colouring that the k-recolouring diameter is linear when k ≥ 2d + 2, which is an already known result [START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF].

Proof of Theorem 1. Note that given a d-degenerate graphs and k colours, we can consider the list assignment L where L(v) = [k] for every vertex v. This list assignment is a-feasible with a = k -d -1.

We start with the second point of Theorem 1. If k ≥ (1 + ε)(d + 1) then:

k a = k k -d -1 = 1 + d + 1 k -d -1 ≤ 1 + 1 ε .
By applying the third case of Theorem 6, the result follows.

The first point follows immediately from the result above by taking ε = 1 2 . Finally, in order to prove the last point, we need to prove that we can "replace" k by d. Let G be a d-degenerate graph and let γ be a (d + 1)-colouring of it. Let us prove that, if k > d + 2, any colouring α can be transformed into γ within O(n d+1 ) steps (and not O(n k-1 ) as suggested by Theorem 6). Indeed, we simply simply "forget" the vertices coloured with colour d + 3, . . . , k in α. Let H be the graph without these vertices. The graph H is d-degenerate and by Theorem 6, we can transform α| H into γ| H within O(n d+1 ) steps using colours in 1, . . . , d + 2. We finally recolour the vertices of G \ H one by one with their colours in γ to obtain the colouring γ.

The rest of this section is devoted to prove Theorem 6. In order to do it, we need to generalise the notion of full colour to the list-colouring setting. We also need to generalise it to sets of colours, to handle the case where a > 1. Given a colouring α of G, the set of colour S is full if for every vertex v and every colour c ∈ S one of the following holds:

(i) α(v) ∈ S, (ii) v has at least one out-neighbour coloured c, (iii) or c ∈ L(v).
We have a property similar as previously: starting from an a-feasible list assignment with a colouring α, if S is full then by removing all the vertices v with a colour α(v) ∈ S from the graph, and removing all the colours from S from all the lists, the resulting assignment is still a-feasible. Additionally, the total number of colours has decreased by |S| (but the degeneracy of the graph might not have decreased as much if we had k much larger than d + 2).

In the following, we will denote by f a (n, k) the maximum diameter of G(G, L) over all graphs G with n vertices, and all a-feasible assignments L with total number of colours k.

The proof of Theorem 6 is by induction on the total number of colours k. The base case, which is the first point of Theorem 6, is the following lemma. This lemma ensures that if the number of excess colours is sufficient (at least half the number of colours), then the diameter is linear3 . Lemma 7. Assume that k ≤ 2a, then f a (n, k) ≤ kn.

Proof. We show by induction on n that if k ≤ 2a + 1, then for any a-feasible list assignment L on a graph on n vertices, and any two L-colourings α, β, there is a transformation from α to β such that every vertex is recoloured at most k times.

The result is clearly true when n = 1, since in this case the unique vertex can be recoloured only once. Assume that the result holds for n -1. Let G be a graph on n vertices with a degeneracy ordering v 1 , . . . , v n , and an a-feasible list assignment L using a total of k colours. Let α and β be two L-colourings, H be the subgraph obtained after removing v n , and define d = |d + (v 1 )| the number of neighbours of v 1 .

Using induction on H, there is a transformation S from α| H to β| H such that every vertex is recoloured at most k times. Note that by assumption, the number of colours available to v 1 is at least d + a + 1, hence the total number of colours k satisfies, d + a + 1 ≤ k ≤ 2a, and in particular a ≥ d + 1, and k ≥ d + a + 1 ≥ 2d + 2. Every time one of the neighbours of v 1 is recoloured in the sequence S, we may have to recolour v 1 beforehand, so that the colouring remains proper. This happens if the neighbour wants to be recoloured with the current colour of v 1 .

Every time we have to recolour v 1 , we have the choice among a ≥ d + 1 colours C for the new colour of v 1 . We can look ahead in S to know which are the next d + 1 modifications of colours of neighbours of v 1 in S. One colour c of C does not appear in these modifications since |C| ≥ d + 1 and the first modified colour is not in C (since we need to recolour v 1 at the first step, and then the target colour is the current colour of v 1 which is not in C). We recolour v 1 with c. This way, we only need to recolour v 1 once out of every d + 1 times its neighbours are recoloured. Finally, we may need to recolour v 1 one last time after the end of S to colour v 1 with its target colour. Since by induction, the neighbours of v 1 are recoloured at most k times, the total number of times v 1 is recoloured is at most:

dk d + 1 + 1 ≤ d d + 1 k + 2 ≤ k ,
where in the last inequality, we have used the fact that 2 ≤ k d+1 since k ≥ 2d+2. This concludes the induction step and proves the result.

In the induction step of our proof, we will build a set of full colours. For a colouring α and a set X of vertices, we denote by α(X) = x∈X α(x). Before stating the main lemmas, let us make the following remark: Remark 1. Let G be a graph, L be a list assignment and α be a L-list colouring. Let H be an induced subgraph of G with list assignment L (v) = L(v) \ α(N (v) \ V (H)). Then any recolouring sequence S from α| H to some colouring β| H also is a (valid) recolouring sequence from α to β where

β(v) = β| H (v) if v ∈ H and α(v) otherwise.
By abuse of notation and when no confusion is possible, we will then call S both the recolouring sequence in H and in G.

The following lemma states that, if we already have a set of full colours, then changing it to an other given set can be done without too many additional recolouring steps. Lemma 8. Let α be a colouring of G, and S a set of full colours for α with |S| = a. For any S with |S | = a, there exists a colouring α such that S is full for α , and there is a transformation from α to α of length at most f a (n, k -a) + (2a + 2)n.

Proof. Let S be a set of colours with |S| = a which is full for some L-colouring α. Let S be any set of colours of size a. The main part of the proof consists in transforming α into a colouring that does not use at all any colour of S (such a colouring exists since the list assignment is a-feasible).

Let H be the subgraph induced by the vertices not coloured S in α, and let L H be the list assignment for H obtained from L by removing S from all the lists. Since S is full in α, L H is a-feasible for H.

Consider the following preference ordering on the colours: an arbitrary ordering of [k] \ (S ∪ S ), followed by an ordering of S \ S, and finally the colours from S last. Let γ be the L-colouring of G obtained by colouring G greedily from v n to v 1 with this preference ordering. Since L is a-feasible, and |S| = a, no vertex is coloured with a colour in S in γ. Indeed |L(v)| ≥ |d + (v)| + a + 1 and only |d + (v)| neighbours of v have been coloured when v is coloured. Since in γ no vertex has a colour in S, γ| H is an L H -colouring of H. By induction hypothesis, there is a recolouring sequence that transforms the colouring α| H of H into γ| H within at most f a (n, k -a) steps. By Remark 1, this recolouring sequence also is a recolouring sequence in G. We can then recolour the vertices of G \ H to their target colour in γ in an additional n steps. No conflict can happen at this step since γ is a proper colouring of G.

One can easily check that, in γ, the set of colours [k]\(S ∪S ) is full. Let K be the subgraph of G induced by all the vertices coloured S in γ, and let L K be a list assignment of these vertices where all the colours not in S ∪ S were removed. Then since [k] \ (S ∪ S ) is full, L K is a-feasible. We will recolour K such that no vertex is coloured S (such a colouring exists because L K is a-feasible, and |S | = a). Since the total number of colours used in

L K is |S ∪ S | ≤ |S| + |S | = 2a
, this recolouring can be done in at most f a (n, 2a) = 2an steps by Lemma 7. By Remark 1, this recolouring sequence also is a recolouring sequence in G. The colouring γ of G that we obtain is such that no vertex is coloured with c ∈ S . We can finally recolour the vertices of G one by one, starting from v n , choosing a colour of S if it is available, or leaving it with its current colour otherwise.

Let α be the resulting colouring. By construction α is full for S . The total number of steps to reach α is at most

f a (n, k -a) + n + 2an + n = f a (n, k -a) + (2a + 2)n.
Using Lemma 8, we show that we can incrementally construct a set of full colours. Lemma 9. Assume that k ≥ 2a. For any colouring α, there exists a colouring β containing a set of full colours S with |S| = a, and there is a transformation from α to β of length at most

n a f a (n, k -a) + 4n 2 .
Proof. Let v 1 , . . . , v n be a degeneracy ordering of G. A colouring is full up to step i for a set of colour S if |S| = a, and all the vertices v j with j ≤ i satisfy the conditions (i), (ii), (iii) for the set S. If a colouring γ is full up to step n for the set S, then the set S is full.

Note that for any colouring α, any set of colours containing α(v 1 ), . . . , α(v a ) is full up to step a. So we only need to show that given a colouring α which is full up to step i for some set S, we can reach a colouring α full up to step i + a for some (potentially different) set S in at most f a (n, k -a) + 4an steps. Suppose now that α is full up to step i but not i + 1 for some set S. Let S be the colours of the vertices v i+1 , . . . , v i+a . Up to adding arbitrary colours to S , we can assume that |S | = a. We will then recolour the graph in order to obtain a colouring where S is full up to step i + a.

Let H be the graph induced by the vertices v 1 , . . . , v i , and L H be the list assignment of the vertices of H obtained from L by fixing the colours of the vertices outside H. In other words, for every vertex v ∈ V (H), we remove from L(v) the colours of all the vertices of N (v) ∩ {v i+1 , . . . , v n }. Note that L H is an a-feasible assignment of H since L was an a-feasible assignment of G. Additionally, S is a set of full colours for the colouring α| H . By Lemma 8, there is an L H -colouring α H of H which is full for S such that we can transform α| H into α| H in at most f a (n, k -a) + (2a + 2)n steps. Let α be the colouring which agrees with α on the vertices with index larger than i, and agrees with α| H on H. By Remark 1, α can be obtained from α into at most f a (n, k -a) + (2a + 2)n steps. By construction, S is full up to step i, and since the vertices v i+1 , . . . v i+a are coloured with colours in S , it is full up to step i + a.

Finally, this procedure needs to be repeated at most n a -1 ≤ n a times (the minus one coming from the fact that at the beginning we had for free a set of colours full for v 1 , . . . , v a ). After this many steps, we obtain a colouring full up to step n for some set S with |S| = a, which concludes the proof.

Finally, we can use the two previous lemma to get the following recursive inequality.

Lemma 10. Let k ≥ 2a, then f a (n, k) ≤ ( 2n a + 3)f a (n, k -a) + 10 • n 2 .
Proof. Let L be an a-feasible list assignment of G, and α and β be two L-colourings of G. By Lemma 9, there exists a colouring α and a set of colours S α with |S α | = a which is full for α such that the colouring α can be reached from α in at most n a f a (n, k -a) + 4n 2 steps. Similarly, there exists a colouring β and a set of colours S β with |S β | = a such that S β is full for β such that the colouring β can be reached from β in at most n a f a (n, k -a) + 4n 2 steps. By Lemma 8, using an additional f a (n, k -a) + 4n steps, we can get a colouring β from β such that the set of full colours in β and α is the same (namely S α ).

Let S be some set of colours disjoint from S α with |S| = a. Let γ be a colouring of G that does not use any colour of S α (such a colouring exists since the list assignment of G is a-feasible).

Let G α be the graph G where the vertices coloured with colours in S α have been deleted and the colours in S α removed from the list assignment. Since S α is full for α , the list assignment of G α is a-feasible. Note that γ| Gα is a proper colouring of G α . So by induction, it is possible to recolour α | Gα into γ| Gα in at most f a (n, k -a) steps. Since the vertices of W := V (G) \ V (G α ) are coloured with colours in S α , and since γ does not use any of these colours, one can finally recolour the vertices of W one by one from their colours in S α to their target colours in γ.

Let G β be the graph where the vertices coloured with S β = S α in β have been deleted. One can similarly recolour β | G β into γ| G β in at most f a (n, k -a) steps. Since vertices of W := V (G) \ V (G β ) are coloured with colours in S α , we can also can recolour the vertices of W one by one from their colours in S α to their target colours in γ.

The total number of steps to transform α into β is at most

f (n, k) ≤ 2 n a f a (n, k -a) + 4n 2 + (f a (n, k -a) + 4n) + 2f a (n, k -a) + 2n ≤ 2n a + 3 f a (n, k -a) + 10n 2
Lemma 11. For all k ≥ 1 and a ≥ 1, we have f a (n, k) ≤ Ckn 2n a + 3 k a -2 for some constant C > 0.

Proof. We prove it by induction on the total number of colours k. The base case is when k ≤ 2a and simply is a consequence of Lemma 7 (note that k a = 2 since k > a). The induction step is obtained using Lemma 10.

We now have all the ingredients to prove Theorem 6, which completes the proof of Theorem 1.

• Every face of size at least 6 gives weight 1 3 to all its incident vertices. After applying this transformation, every face has a non-negative weight. Indeed, the faces of lengt 4 still have weight 0, and the faces of length at least 6 gave a total of deg(f )

3 ≤ deg(f ) -4 since deg(f ) ≥ 6.
Vertices of level 2 initially have non-negative weights since their degree is at least four, and they did not give away any of their weights. Hence their weights remain non-negative. Vertices of level at least 3 must have, by definition at least 4 neighbours of degree larger than 3 (otherwise they would be of level 2), and thus keep a positive weight.

Finally, let v be a vertex of degree 3. If v is adjacent to a vertex of level at least 3, it receives weight 1 during the first step, and its weight is non-negative. Otherwise, v is adjacent to three vertices of level at most 2, and then, by assumption on G, the three faces incident to v must have size at least 6. Then, v received 1 3 from each of the faces during the second step, and its weight is non-negative.

Hence, after applying the the procedure, every face and every vertex has a non-negative weight, a contradiction with the fact that the total weight is negative.

We can now prove the Theorem 2. The proceeds by iteratively reducing the size of the graph, either by removing a vertex, or contracting two vertices together.

Proof of Theorem 2. We will show by induction on the size of the graph G that for any two 5 colourings of G, α and β, there exists a transformation from α to β such that each vertex is recoloured at most cn times, for some constant c defined later.

If G is reduced to a single vertex, the result is immediate. Otherwise, let n > 1. One of the two conditions of Lemma 12 must occur. Case (i). The graph G contains a vertex v of degree at most 2.

Let H be the subgraph obtained after removing v. By induction, there exists a transformation S from α| H to β| H such that each vertex is recoloured at most c(n -1) times. Given this transformation, we are going to produce a transformation S for the whole graph G. We follow the transformation steps of S. If the same recolouring step is possible in G we do it. Otherwise, it means that one of the (at most) two neighbours of v is recoloured, and that the target colour is the current colour c of v. So we need to recolour v to make the transition possible. To recolour v, we have at least two possible new colour choices X for v distinct from c. We can look forward at the sequence S to see which colour c will appear next in the neighbourhood of v. We choose for v a colour of X distinct from c . In particular, the choice of c ensures that v will not be recoloured next time a neighbour of v is recoloured. At the end of the transformation S, we may need one additional step to recolour v to its target colour.

Thus in total, v is recoloured at most 2c(n-1) 2 + 1 ≤ cn times (which holds as long as c ≥ 1). Case (ii). The graph G contains a vertex v of degree three such that:

• all three neighbours of v have level at most 2,

• v is incident to a face of length 4.

Let f be the face of length 4 incident to v, and let w be the vertex opposite to v on f . Let u be the vertex adjacent to v, and not incident to f . Let v 1 and v 2 be the two remaining vertices adjacent to f (see Figure 2). In this case, we want to reduce the graph by merging the two vertices v and w (maintaining a bipartite planar graph). For this we will need the following result. Claim 13. Starting from α, we can reach a colouring α such that α (v) = α (w). This colouring can be reached by recolouring each vertex at most twice.

Proof. Since v 1 and v 2 are adjacent to w, their colour is different from α(w). Hence, the only obstruction to recolour directly v with α(w) is if u is coloured with α(w). Since u has level at most 2, it has at most 3 neighbours with degree larger than 3. Let c be a colour different from these three neighbours, and different from α(w). First, we recolour all the degree three neighbours of u which are coloured c with any other colour (note that w is not recoloured since α(w) = c, but v might be recoloured). Then, we recolour u with c, and finally v can be recoloured with α(w) (since G is bipartite, the recolouring sequence ensures that the only neighbor of v that is recoloured is u). Every vertex is recoloured at most once, except v which may be recoloured twice.

By Claim 13 starting from α and β, we obtain two colourings α and β such that α (v) = α (w) and β (v) = β (w). Let H be the graph obtained after merging v and w into a single vertex x. Clearly H is still planar, and it is still bipartite since v and w are on the same side of the bipartition of G. Moreover, α and β are proper colourings of H. By induction, there is a transformation from α to β in H such that each vertex is recoloured at most c(n -1) times. By applying each transformation on x to both v and w, this gives a transformation in G from α to β such that each vertex is recoloured at most c(n -1) times.

This gives a transformation from α to β where each vertex is recoloured at most c(n-1)+4 ≤ cn times, taking c = 4.

2 fFigure 2 :

 22 Figure 2: Reducible configuration in case (ii).

Actually, it only gives the irreducibility of the chain. To get the ergodicity, we also need the chain to be aperiodic. For the chains associated to proper graph colourings, this property is usually straightforward.

The proof is similar to the linear diameter obtained in[START_REF] Bousquet | Fast recoloring of sparse graphs[END_REF] for colourings but adapted to list colourings.

* This work was supported by ANR project GrR (ANR-18-CE40-0032).

Proof of Theorem 6. The first point is the result from Lemma 7. The second and last points are consequences of Lemma 11 with the corresponding values of a. Let us prove the third point. Since

Consequently, the function given by Lemma 11 is O(n 1/ε ). Note that for the second and third point, the constant does not depend on k or a since k/a is a constant (but it depends on ε in the third point).

Planar bipartite graphs

The rest of this article is devoted to prove Cereceda's quadratic conjecture for planar bipartite graphs.

Theorem 2. Let G be a planar bipartite graph. The diameter of G(G, 5) is at most 4n 2 .

We start by defining the level of a vertex. Given a graph G all the vertices with degree at most 3 have level 1. For any i > 1, the vertices with level i are the ones with degree at most 3 after removal of all the vertices of level j < i.

Let G be a planar graph given with its representation. The size of a face is the number of vertices incident to the face. The proof of Theorem 2 is based on a discharging proof. We are assuming that the results does not hold. The proof then goes in two steps. First, we show that any planar bipartite graph must contain at least one "configuration" of a list of (here two) configurations. Then, we prove that any counter-example cannot contain any other these configurations, which implies that this counter-example cannot exist. Let us first give the two configurations we will need.

Lemma 12. Let G be a planar bipartite graph. At least one of the following holds:

(i) G contains a vertex of degree at most 2 or, (ii) G contains a vertex of degree 3 incident to three vertices of level at most 2, and incident to a face of size four.

Proof. We use a discharging argument to prove the result. Suppose by contradiction that there exists a planar bipartite graph G satisfying none of the conditions above. Assign to each vertex v the weight deg(v) -4, and to each face f the weight deg(f ) -4. The total weight assigned this way is:

where n, |E| and |F | are the number of vertices, edges, and faces of G. The last equality comes from Euler's formula for planar graphs. Now the goal is to re-allocate the weights on the faces and the vertices to obtain a total weight that is non-negative, a contradiction with the equation above. Note that all the faces as well as vertices of degree at least 4 have non-negative weights. In order to get a contradiction, we apply the following procedure and prove that after applying it all the vertices and faces have non-negative weights:

• Every vertex of level at least 3 gives weight 1 to all its neighbours of degree 3.


Alexis Lossouarn

Chloé Puteaux

Laetitia Bailly

Vincent Tognetti
email: vincent.tognetti@univ-rouen.fr

Laurent Joubert

Pierre-Yves Renard

Cyrille Sabot
email: cyrille.sabot@univ-rouen.fr

Dr C A Lossouarn

L Puteaux

Prof L Bailly

Dr V Joubert

Prof. P.-Y Tognetti

Dr C Renard

Sabot

Metalloenzyme-Mediated Thiol-Yne Addition towards Photoisomerizable Fluorescent Dyes

Proteins are able to irreversibly assemble biologically active ligands from building blocks bearing complementary reactive functions due their spatial proximity, through a kinetic target-guided synthetic process (also named in situ click chemistry). Although linkages thus formed are mostly passive, some of them have shown to significantly contribute to the protein binding through for instance hydrogen bonding and stacking interactions. Biocompatible reactions and click chemistry are a formidable source of inspiration for developing such new protein-directed ligations. In this study, we report a proximity-induced thiol-yne synthesis of carbonic anhydrase inhibitors. Not only this example widens the arsenal of Kinetic target-guided synthesis (KTGS) eligible reactions, but the obtained product displayed unsuspected photophysical properties. The corresponding vinyl sulfide linkage conjugated to a coumarin core proved to be engaged in a monodirectional Z to E photoisomerization process. Further investigations guided by theoretical calculations showed that fine-tuning of the nature of the substituents on the coumarin moiety allows to obtain a bidirectional photochemical process, thus discovering a new photoswitching moiety, displaying moreover fluorescence properties. Due to the spectral tunability of coumarin derivatives, this work should open new opportunities for the design of vinyl sulfide-based photoswitch systems with modular photophysical properties.

Introduction

Drug discovery is repeatedly facing the challenge of finding new biological targets, pharmacophores, or elucidating novel mechanisms of action, in a time-and cost-effective manner. [START_REF] Aldewachi | [END_REF] This interdisciplinary field of research benefits from constant innovations in biophysics (X-ray crystallography, NMR & surface plasmon resonance (SPR) spectroscopy, isothermal titration calorimetry (ITC)), [2] in computing technologies, including machine learning processes opening new frontiers to yet underexploited scaffolds, [3] in high-throughput screening with wide range of sophisticated assays and automated evaluation of large numbers of chemical/biological compounds. [4] Important advances in drug design have also been achieved with contributions from chemistry, in particular with the diversity-oriented synthesis which generates structural diversity in an efficient manner, [5] and with the kinetic target-guided synthesis (KTGS) strategy which allows the synthesis and the identification of potent pharmacophores in a single step process. [6] In KTGS, the biological target is able to assemble its own ligands by linking together two fragments bearing complementary reactive chemical functions due to their spatial proximity. This technology enabled the discovery and/or optimisation of bioactive molecules with more than 50 examples, covering 10 different therapeutic areas. [6e] Importantly, this method allowed the identification of unknown protein conformations, [7] or previously hidden binding pockets. [8] A handful of chemical ligation strategies have been reported to form a covalent bond between recruited fragments within the binding pocket of biological targets, among which the alkyne-azide 1,3-dipolar cycloaddition reaction leading to the formation of 1,4-or 1,5-triazole linkages has been used predominantly. [9] The triazole ring system has shown to offer a substantial additional and beneficial binding contribution with π-π stacking and hydrogen-bonding interactions. [7] More recently, Rademann and co-workers also highlighted a superadditive fragment combination through a protein-induced Mannich ligation. [10] Recent developments in protein-templated chemistry also include the amidation from activated carboxylic acids and amines, [11] the Knoevenagel reaction, [12] and the Ugi four-component reaction. [13] Other ligation strategies can be implemented by drawing inspiration from biocompatible and click chemistry portfolio reactions used in bioorthogonal bioconjugate processes, by tuning their kinetics to meet the requirements for use in KTGS strategies. [14] This can be achieved by structural modifications of the reactive partners in order to decrease their reactivity [15] or by removing the catalyst such as in the alkyne-azide click chemistry. [9] In this context, thiol-yne [16] click chemistry would offer attractive features such as the small size of the reactive moieties, the accessibility and apparent robustness of the alkyne group, and the requirement of additives or catalysts such as amines, [17] transition metals [18] or photoinitiators [19] to promote the reaction. This strategy has found key roles in polymer chemistry, biomaterials synthesis and surface modifications. [20] Importantly, Ovaa [21] and Mootz [22] have independently used alkynes as latent electrophiles for the design of covalent inhibitors upon their reaction with thiol group of enzymes, which contain an active site cysteine (Figure 1A). These important results show that the thiol-yne reaction can be triggered by a proximity effect (i.e., without any other external activation). This and other considerations discussed above prompted us to investigate this reaction as a new plausible ligation tool for the protein-directed synthesis of ligands (Figure 1B). In this study, we illustrate the potential of the thiol-yne addition in KTGS through the implementation of this click reaction to a model metalloenzyme whose specific inhibition is of interest for the treatment of several diseases.

Results and Discussion

Carbonic anhydrase II (CA-II) selected as the model protein to evaluate the potential of thiol-yne reaction in KTGS is a zinc-containing metalloenzyme that catalyses the reversible hydration of carbon dioxide (CO2) to generate bicarbonate (HCO3 -) and a proton (H + ), through a metal hydroxide nucleophilic species. The zinc ion is located at the bottom of a 16 Å deep canonical active site, where it is tetrahedrally coordinated by three imidazole groups of His residues and by one hydroxide ion. CA is ubiquitous in numerous tissues, and involved in a variety of physiological processes, including pH regulation, gas exchange, ion transport, bone resorption, fatty acid metabolism. Inhibitors of CAs are clinically used for the treatment of glaucoma, oedema, altitude sickness, and epilepsy. [23] Up-regulation or overexpression of CAs may be associated with physiological disorders such as tumours, and neurodegenerative pathologies such as Alzheimer disease. [24] Sulfonamides are an important class of CA inhibitors due to their effective binding to the zinc(II) ion, thereby preventing the binding of the endogenous CO2 and H2O substrates. [25] Accordingly, in this study, a readily accessible αmercaptotosylamide 1a playing the role of anchor was incubated with a series of aliphatic-2a-d or aromatic alkynes 2e-h as binary mixtures, in parallel of negative controls without enzyme (Figure 2). Alternatively, the alkyne-bearing sulfonamide 4-ethynylbenzenesulfonamide 2f was incubated with heteroaromatic thiols 1b, 1c or the thiobenzyl alcohol 1d. The crude reaction mixtures were analysed by LC-MS/MRM or LC-HRMS and compared with products obtained from chemical synthesis.

Hit discovery

From this study, a ~2-to 10-fold acceleration (depending on the protein reference and batch, see SI section 7, S45-50) of the thiol-yne addition reaction between 1a and 2h leading to the vinyl sulfide 3ah (as a mixture of diasteoisomers Z/E: 89:11) was observed, as compared with the control experiments carried out in the absence of bCA-II. No trace of the Markovnikov thiol-yne product (Figure 1B) was detected, nor in the untemplated reaction. Of note, the formation of 3ah, although in the subnanomolar range, was significantly affected by the presence of acetazolamide ATZ or ethoxazolamide ETOX (3.3 equivalents relative to the active-site binder 1a), two highly effective commercially available active-site bCA-II submicromolar inhibitors. Moreover, the reaction carried out between the non-zinc coordinating analogue 1d of 1a, and 2h was not accelerated in the presence of bCA-II. Together, these results confirmed that templated reaction occurred in the active site of the bCA-II and not in another hidden pocket or binding site. Then, the biological activity of templated products Z-3ah and E-3ah was evaluated through 4-nitrophenyl acetate hydrolysis assays (see SI section 9, S62) [26] by measuring their half maximal inhibitory concentration (IC50), which was found to be 0.33 ± 0.01 and 0.55 ± 0.07 M, respectively, while acetazolamide ATZ, has an IC50 value of 0.14 ± 0.02 M (Figure 2). A flexible thioether analogue 10 was prepared in order to investigate the impact of the rigidity of the vinyl sulfide linkage of 3ah on the biological activity, and its activity (0.36 ± 0.07 M) was found to be in the range of that of the most active Z-3ah. The stability of the vinyl sulfide linkage of 3ah was investigated in the presence of biothiols (N-acetyl cysteine, glutathione), as well as in human blood plasma (HBP) after a few days of incubation at 37 °C. Neither thiol release nor degradation was noticed, which confirms the stability of 3ah and the irreversibility of the reaction under physiological conditions. In contrast, the thioether analogue 10 was partially oxidized (~5%) into the corresponding sulfoxide after incubation in HBP at 37 °C for 3 days (see SI section 8.1 S51-61).

While the starting 7-ethynylcoumarin was not emissive in PBS, [27] both 3ah isomers displayed fluorescence properties, with very similar absorption and emission spectra (Figure 3A and 3B). They exhibited a relatively high emission wavelength (510 nm) and an unusual large Stokes shift (155 nm) for low molecular-weight coumarin derivatives. [28] However, their fluorescence quantum yields are significantly different with 0.16 and 0.52 for Z-3ah and E-3ah, respectively in PBS pH 7.4. Whilst the absorption spectrum displays a minor change with decreasing polarity of the solvent, a hypsochromic shift (up to 88 nm) of the fluorescence emission spectrum was observed (Figure 3C and see SI section 10.5 S72-74). These unusual optical features were found to be particularly suitable for their use in the intrinsic Förster Resonance Energy Transfer (iFRET) technique, [29] which could further support the existence of specific protein-ligand interactions between CA-II and the vinyl sulfide inhibitor 3ah. In fact, the iFRET approach uses a FRET mechanism between endogenous tryptophan (Trp) residues (λabs ~ 280 nm, λem ~ 310-350 nm) that are in close proximity to fluorescent ligands bound in the active site of target proteins, which act as donor (D) and acceptor (A), respectively (Figure 4A). However, the limited Stokes shift of reported probes used in such iFRET experiments such as 1-naphthylamine or 7-hydroxycoumarin dyes are subject to self-absorption, [30] or display low sensitivity such as the dansyl moiety, [31] which decreases the FRET efficiency. Accordingly, the use of vinyl sulfide-based coumarin as a new acceptor in Trp-FRET was examined in order to address these issues. First, excitation of Trp residues at 280 nm of a solution of bCA-II (2 M) in PBS (pH 7.4) led to an emission band centred at 336 nm. This emission peak significantly decreased in the presence of Z-3ah (2 or 4 equiv.), evidenced by an iFRET efficiency E of 86%, which was determined from the equation E = 1 -IDA/ID (where IDA and ID are the intensities of the donor D in the presence or in the absence of the acceptor A, respectively) (Figure 4B). [29] A) Moreover, Z-3ah undergoes a 15 nm hypsochromic shift in the emission spectrum upon binding to bCA-II (from 510 to 495 nm), which, together with Z-3ah solvatochromic character is consistent with a hydrophobic environment surrounding the fluorophore in the CA active site. Next, as negative controls, Z-3ah was incubated with different non-target proteins as binary mixtures, including porcine liver esterase (pLE), lysozyme (LYZ), bovine serum albumin (BSA), concanavalin A (ConA) and papain (Figure 4C). None of them led to a significant fluorescence enhancement in the probe region compared with the probe alone, a result which also indicates the probe's specificity for the bCA-II binding site. Only BSA displayed a 2-fold increase in fluorescence intensity, which could be associated to non-specific probe-protein interactions. This is often observed with this major small molecules binding protein, which size and collection of non-specific binding sites are used to transport a wide range of fluorophores or drug like small molecules and even to solubilize dye aggregates. [32] Finally, the fluorescence response of a solution of Z-3ah (1 M) towards a mixture of these five non-target proteins (2.5 M each) was investigated. No significant fluorescence was observed in the 500 nm region (in blue, Figure 4D) whereas the fluorescence intensity of probe Z-3ah showed a 10-fold increase in this spectral region when bCA-II (2.5 M) was present in the protein mixture (in black, Figure 4D). Of note, in the presence of ATZ (100 M), no more significant iFRET signal was detected (in red, Figure 4D).

Wavelength (nm)

During preliminary studies, we also observed an E to Z isomerization of the vinyl sulfide double bond of 3ah in aqueous solution upon exposure to ambient light, at room temperature. This photophysical behaviour caught our attention and was further investigated, as only few chemical scaffolds have been reported to undergo such catalyst-free reversible photoisomerization despite the increasing importance of photoswitch systems for the fine control of materials and biological systems properties [33] with applications in drug delivery, [34] bio-imaging, [35] or in the development of hydrogels. [36] Major classes of photoswitchable molecules include azobenzenes, [37] stilbenes, [38] diarylethenes, [39] or spiropyranes, [40] and emerging systems such as hydrazones, [41] iminothioindoxyls. [42] Among them, azobenzenes received considerable attention due to their straightforward synthetic access and good photo-fatigue resistance, although substantial efforts have been devoted to overcome shortcomings such as short thermal half-lives of Z-isomers (metastability), and incomplete reverse Z to E photoisomerizations due an overlap of the n* bands of E and Z isomers. In this present study, the conversion of the Z-isomer into its E-form was first confirmed by [START_REF] Aldewachi | [END_REF] H NMR spectroscopy studies upon the exposure of an isomeric mixture of 3ah (Z/E 70:30) to ambient light source, which shifted the ratio in favour of the E-isomer (45:55) (dotted curve, Figure 5A). Starting from the pure Z isomer, a photostationary state (PSS) containing 82% of the E isomer was rapidly reached in aqueous system, under 365 nm LED spotlight irradiation (continuous curve, Figure 5B). This PSS isomeric composition was confirmed by irradiating the pure E isomer, which underwent isomerization reaching the same equilibrium state (Figure 5B). Then, the photostationary 380, 405, 450 nm). In all these studies, the E isomer was obtained preferentially, albeit with different proportions (PSS380 nm = 77%; PSS405 nm = 73%; PSS450 nm = 64%). A monochromatic excitation at 300 nm, or 450 nm by using a xenon lamp coupled with a monochromator did not increase the proportion of Z isomer. From these results, it was, however, anticipated that reversible photoisomerization would occur but with a low amplitude as shown in Figure 5C, upon alternating the irradiation wavelength between 365 and 450 nm. The Z isomer has shown to be highly stable in the dark and can be kept for several months at room temperature without noticeable isomerization. Thermal conditions (80 °C for 2h) did not enable Z to E isomerization, which was also confirmed by density functional theory (DFT) calculations since the ground state activation barrier for this step was found to be equal to 61 kcal mol -1 in pure implicit DMSO in terms of standard Gibbs energy with respect to E diastereoisomer, which is 1.6 kcal mol -1 more stable than the Z diastereoisomer (see SI section 13.6, S167). Although vinyl sulfide coumarin 3ah still constitutes a rare example of fluorescent molecules with a photoswitchable character, [41,43] the low E to Z photoconversion prevents any important applications in this field. Therefore, as a natural extension of these studies, we questioned whether further optimization, guided by theoretical studies, would be possible. Indeed, the strong overlap of the absorption spectra of both isomers, prevents Z enriched PSS. This issue may be circumvented by the introduction of specific chemical functions (electron withdrawing or electron donating groups) on the coumarin ring at positions 3, 4, that are known to significantly alter its absorbance. [28,44] Besides, the introduction of chemical functions at position 6, and/or 8, that are at the ortho-position of the vinyl sulfide moiety, may intuitively cause a distortion of the planar Z isomer, thus affecting specifically its   * transition. These features can be tackled from a quantum chemistry point of view using time-dependent DFT (TD-DFT, see SI section 13.1, S108 for the computational details). To this aim, eight common substituents, representative of inductive and mesomeric electron withdrawing or -donating moieties were considered (CH3, CF3, CN, CO2H, OCH3, F, Cl, Br) and tested at each of these positions. Note that in order to understand the role of a given site, hydrogen atoms only were first considered on the three remaining positions. Besides, for the sake of simplicity, only the s-trans conformation of the C=C double bond linking the coumarin to the sulfide moiety was investigated, as represented in Figure 6. Due to steric hindrance, such a conformation does not actually allow accommodating the CF3, CO2H, Cl and Br substituents in position 6, so that the vertical absorption wavelengths (corresponding to the ground state to the first electronic excited state transition) for Z and E isomers were computed for 28 mono-substituted compounds in implicit pure DMSO solvent (coordinates and energies are collected in sections 13.2 and 13.3 in SI).

As shown in Figure 6 and in section 13.5, S166, the absorption wavelength is lower for the Z-than for E isomer in almost all cases (only 5 exceptions), and there are only two of them that feature a significant  difference: 35 nm for R 6 = CN and 19 nm for R 6 = F. Noteworthy, in both cases, the Z isomer is far from being planar (the C a C b C 7 C 6 dihedral angle being equal to 69° and 46°, respectively). Moreover, all substitution patterns exhibiting a value higher than 5 nm, involve a Z isomer for which ∠C a C b C 7 C 6 is higher than 35°. However, this non-planarity condition, while necessary, is not sufficient One may also wonder whether a simple molecular orbital (MO) analysis could be used instead of this more timeconsuming TD-DFT approach. As shown in section 13.4, S165, the frontier canonical Kohn-Sham MO gap, gap, is nicely linearly correlated to the absorption wavelength according to hcgap with a mean absolute error equal to 3 nm.

However, such an approach would be inefficient for accurate screening. Indeed, it reveals unsatisfying to predict wavelength differences and even their correct sign. For instance, for R 8 = CH3, it gives = +5 nm, while the TD-DFT value is -6 nm. Secondly, the slope of this linear model is a little bit far from 1.0, suggesting that the electronic transition might be more complex than a simple HOMO→LUMO transition. Indeed, even if, for most systems, this mono-electronic transfer (as expected of the 𝜋 → 𝜋 * type, as pictured in section 13.7, S171) represents about 85-90% of the transition, it only describes 75% and 82% of it for Z isomer with R 6 =CN and F respectively, which are, as previously mentioned, the most promising systems.

However, while featuring the highest  value, R 6 = CN is subsequently disqualified by its low value for the Z absorption wavelength (297 nm), which is actually too far from the visible spectrum, precluding its practical use in a biological context. We thus turned out attention to the fluorine substitution. Interestingly, adding another fluorine atom in position 8 resulted in a non-negligible increase (compound #29 in Figure 6) of the wavelength separation, leading to  = 23 nm. However, from a synthetic point of view, adding a methyl group in position 4 leads to a much more straightforward synthesis (see below), with a very slight increase of the  values (24 nm, compound #30 in Figure 6) and keeping the significant nonplanarity (∠C a C b C 7 C 6 = 48°, coordinates and views in section 13.8 in SI).

In order to experimentally verify this theoretical screening strategy, the synthesis of the 4-methyl-6,8-difluorocoumarin 17 (i.e. compound 29 : R 3 = R 4 = H, R 6 = R 8 = F, Figure 6) was achieved in 5 steps and 33% overall yield from commercially available 2,4-difluororesorcinol, and obtained as a mixture of Z/E diastereoisomers (63:37), that were separated by RP-HPLC (see SI section 4.2, S19). Isomers Z-and E-17 in hand, their biological activities were determined and found to be 0.30 ± 0.05 and 0.99 ± 0.11 M, respectively, thus demonstrating that the presence of an extra methyl group (position 3) and two fluorine atoms (position 6 and 8) did not significantly alter the biological activity of the reference compound 3-ah. Regarding the photophysical properties of 17 (Figure 7A-B), satisfyingly, a ~20 nm bathochromic shift of the absorption maximum of the Z isomer (max 337 nm) was observed with theoretical predictions (305 and 329 nm, respectively, in pure implicit DMSOexperimental values being recorded in a H2O-DMSO mixture), proving the reliability of the computational protocol for semiquantitative screening. Both isomers were fluorescent with emission maxima at 495 nm, and a quantum yield of 0.06 and 0.22 for Z-17 and E-17, respectively. Then, the composition of the PSS was investigated upon the irradiation of 17 at different wavelengths (300, 350, 400, 450 nm) with a xenon lamp coupled with a monochromator (see SI). Using light at 300 nm, Z-17 photoswitched to generate a PSS of 65% E isomer. Conversely, E-17 underwent a remarkable E to Z photoisomerization under irradiation at 450 nm providing the Z isomer with a PSS of 87% (Figure 7C). Noteworthy, LEDs did not provide effective Z to E isomerization (see SI section 12.8, S103-104).

TD-DFT calculations were then carried out to cast the light on the physico-chemical origin of this conversion. To this aim, vertical excitations were performed along the minimum energy reaction path (monitored by intrinsic reaction coordinate ) for the ground state S0 isomerization process to approximate excited state potential energy surfaces (PESs), as depicted in Figure 8 (note that the rotation itself around the C=C double bond mainly occurs in the small [-5; 5 amu 1/2 bohr]  range, see right vertical axis). The S0 and second excited state S2 energy profiles display a similar shape with a maximum around ∠HCCH = 90°. The corresponding activation barriers from E isomer (which is the thermodynamically most stable one) were found respectively equal to 55 and 26 kcal mol -1 .

Conversely, the energy is minimal at this point for the first excited state S1. The PES topology corresponds with a conical intersection (CI) with the ground state, allowing a non-radiative transition between S1 and S0. The photo-induced E → Z isomerization mechanism is thus the following: (i) vertical excitation from E to E*, (ii) reaching the highest local point A1*, a step that requires an activation energy equal to only 11 kcal mol -1 (less than 0.5 eV), (iii) reaching the CI zone, (iv) non-emissive transition to S0, (v) vibrational structural relaxation towards either E-or Z isomer. Obviously, evaluating the rate constants and branching ratios of such steps are clearly outside the scope of this static approach, which is however able to qualitatively account for the observed isomerization process and that is fully consistent with similar mechanisms reported for stilbenes. Altogether, these results demonstrate that vinyl sulfide patterns can be subject to effective bidirectional photoconversion and that in aqueous systems. The progress of the E to Z photoisomerization process was followed by recording the absorption spectra of the reaction at different times (Figure 7D). As the reaction progresses, the maximum absorption peak at 355 nm, corresponding to the * transition of the E isomer, decreases and shifts towards higher energy to stabilize at 337 nm corresponding to the isomeric mixture at PSS450 nm (Z/E, 88:12). Figure 7E highlights the good photofatigue-resistance of 17 upon several photoisomerization cycles. Finally, no Z to E isomerization was observed when Z-17 was incubated at 20 or 40 °C in the darkness for more than 50 days, which further illustrates the robustness of vinyl sulfide pattern (see SI section 12.10, S106-107).

Conclusion

This work reports (1) an unprecedented thiol-yne protein-assisted KTGS ligation on small, accessible alkyne and thiol partners, which enabled (2) the identification of a submicromolar inhibitor of bCA-II. It is worth noting that we identified thiol-yne reaction as a potential candidate for KTGS in a recent study evaluating tailored bioorthogonal and bioconjugate chemistry as potential source of inspiration to discover new KTGS eligible reactions. [14] We also found (3) that the vinyl sulfide linkage, formed by the addition of thiol to alkyne groups, is an effective, yet unexplored, electron-donating group for the design of coumarin based fluorophores with large Stokes shifts, with potential applications in bio-imaging or biological target identification in complex media.

Besides, (4) this work underscored the bidirectional photoswitching behaviour of these fluorescent vinyl sulfides coumarine derivatives in aqueous systems, whose -(5) spectral properties could be fine-tuned by structural modifications guided by a theoretical in-silico design. In this context, it was observed that the introduction of fluorine atoms in ortho position on the coumarin ring caused a ~20 nm splitting of E and Z isomers' * bands, which enabled effective bidirectional photoconversion of thermally bistable isomers. The Z to E photoisomerization required UV light, which may temper the impact of this approach for some biological applications. However, the red shift of spectral bands of coumarins by modifications of the lactone ring are well documented, [28,44] moreover we also noticed from theoretical considerations that such modifications should not impact the maximum absorption wavelengths difference between the E and Z isomers. Thus, as a direct perspective, the development of fluorescent vinyl sulfides conjugated to coumarin rings capable of photoswitching exclusively under visible light excitation could be envisioned.

Experimental Section

General remark: Unless otherwise stated, all chemicals were used as received from commercial sources without further purification. bCA-II was purchased from Merck-Sigma-Aldrich (reference C2624, lyophilized powder >95% SDS-PAGE, specific activity ≥3,500 W-A units/mg protein; and reference C2522, lyophilized powder, ≥3,000 W-A units/mg protein) and was stored at -20 °C. Triethylamine and diisopropylethylamine (DIPEA) were distilled over KOH and CaH2, respectively. Solvents, unless otherwise stated, were purchased in reagent grade or HPLC grade and used as received. Dry solvents were obtained following standard procedures: N,N-dimethylformamide (DMF) was purchased as dry solvent from Fisher Scientific and stored over 3 Å molecular sieves; Tetrahydrofuran (THF) was distilled over sodium/benzophenone; Dichloromethane (DCM), acetonitrile (ACN), toluene and diethylether were obtained from MB SPS-800 apparatus from MBRAUN ; isopropanol, methanol and acetone were stored over molecular sieves (3 Å or 4 Å according to the solvent) prior to use. For non-aqueous reactions, flasks were dried by heating with a heat gun under vacuum. All reactions were monitored by thin layer chromatography (TLC) and/or RP-HPLC. TLC were carried out on Merck DC Kieselgel 60 F-254 aluminum sheets. Visualization of spots was performed under a UV lamp at λ = 254 or 365 nm, and/or staining with a KMnO4 solution/K2CO3 + 5% NaOH, developed with heat. Flash column chromatography purifications were performed manually on silica gel (40-63 µM) under pressurized air flow. Aqueous buffers such as tris(hydroxymethyl)aminomethane (Tris) (pH 7.6, 0.05 M), phosphate buffer salin (PBS) (pH 7.4, 0.1 M) or phosphate buffer (PB) (pH 7.4, 0.25 M) and aq. mobile phases for HPLC were prepared using water that was purified with a Milli-Q system (purified to 18.2 MΩ cm) and were stored at 4 °C. Formic acid (FA) for mobile phases was purchased in HPLC grade (Fisher Scientific or Acros Organics) and stored at 4 °C. For LC-MS analyses, ultrapure water (Alfa Aesar, LC-MS quality) was employed for the preparation of mobile phases.

Instruments: 1 H, 19 F and 13 C NMR spectra were recorded on 300 MHz Bruker FT-NMR machine operating at ambient probe temperature. High Resolution Mass spectrometry (HRMS) for compounds characterization was performed with a Waters Micro-mass LCT Premier XE® equipped with an orthogonal acceleration time-of-flight and an electrospray source in positive or negative mode. Infrared spectra were recorded with a universal ATR accessory on a Perkin-Elmer Spectrum One FT-IR spectrum 100 spectrometer. Melting points were recorded on a LEICA VMHB Kofler system at atmospheric pressure and without correction. UV-Vis spectroscopy was performed on an Agilent Cary 60 UV-Vis® at 20 or 25 °C. Fluorescence spectroscopic studies (emission/excitation spectra) were performed on a Horiba Scientific Fluorolog® spectrophotometer, equipped with a Hamamatsu photomultiplier tube R13456 and a xenon 450 W illuminator. Centrifugations were performed with a VWR MicroStar 12® (11 000 rotations/min for 30 min). For bCA-II inhibition assay, the inhibitory activity (IC50) was evaluated spectrophotometrically at 25 °C using a SPARK® Tecan apparatus and 96 well microplates (Eppendorf). p-Nitrophenyl acetate (PNPA) for biological assays was recrystallized from EtOH prior to use and was stored at -25 °C. For KTGS experiments, incubations were conducted in a dedicated oven in which the temperature was maintained to 37 °C.

Representative procedure for the synthesis of vinyl sulfides 3ah and 17: To a solution of 4-(mercaptomethyl)benzenesulfonamide 1a (0.29 mmol, 1 equiv.) in dry MeCN (3 mL) under argon atmosphere was added the corresponding 7-ethynyl-2H-chromen-2-one (0.33 mmol, 1.1 equiv.). The flask was protected from light and 1,8-diazabicyclo[5.4.0]undec-7-ene (DBU) (0.09 mmol, 0.3 equiv.) was added. The reaction was stirred at room temperature for 2.5 h. Then, reaction was quenched with water and extracted with EtOAc ( 2). The combined organic layers were washed with brine ( 1), then dried over MgSO4 and the solvents were removed by vacuum. The crude product was purified firstly by flash-column chromatography (silica gel, DCM/EtOAc as a gradient from 100:0 to 98:2, 95:5 and 90/10, v/v) to provide the desired isomers Z and E as a mixture. Then, both isomers were separated by RP-HPLC (System E) and fractions were collected and lyophilized to provide the desired compounds. (CAUTION! Every steps described above were performed under a complete protection from light) All other characterization data, original spectra, etc., as well as all computational details, are provided in the Supporting Information.

Figure 1 .

 1 Figure 1. Thiol-yne reaction used for A) covalent cysteine protease inhibition, B) proteins-directed inhibitors synthesis (KTGS).

Figure 2 .

 2 Figure 2. Library of KTGS experiments between thiols (60 M), alkynes (400 M), bCA-II (30 M).

Figure 3 .

 3 Figure 3. Photophysical properties of vinyl sulfide coumarin 3ah. A) Relative absorption of Z-3ah (-) and E-3ah (---) in H2O/DMSO 1:1 (v/v) at 25 °C; B) Relative emission of Z-3ah (-) and E-3ah (---) ex 350 nm in H2O/DMSO 1:1 (v/v) at 25 °C; C) Photograph of E-3ah (10 M) in different solvents under UV light (ex = 365 nm).

Figure 4 .

 4 Figure 4. Analysis of Trp-FRET experiments. A) iFRET principle; B) Fluorescence emission spectra of a solution of bCA-II (2 M) in the absence (in blue), or in the presence of Z-3ah (2 M in red, 4 M in black), upon an excitation at 280 nm, in PB pH 7.4; C) Relative fluorescence intensity observed at 495 nm of a solution of Z-3ah (1 M) in the presence of various proteins (2.5 M), upon an excitation at 280 nm, in PB pH 7.4; and D) fluorescence emission of Z-3ah (1 M) in a solution containing five Z -3ah non-target proteins (PCE, LYZ, BSA, ConA, papain, 2.5 M each) in the absence (in blue) or in the presence of bCA-II (2.5 M, without ATZ in black; or with 100 M ATZ in red), upon an excitation at 280 nm, in PB pH 7.4.

  upon the irradiation of Z-3ah with blue visible LEDs of different wavelengths (

Figure 5 .

 5 Figure 5. Photoisomerization studies of 3ah. A) Partial 1 H NMR (DMSO-d6/D2O 75:25, 300 MHz, 298 K) showing the lactone region (H1) of 3ah at t=0 (Z/E, 70:30) and after 2h (Z/E, 45:55) irradiation under ambient light source; B) Time-course of photoisomerization of Z-3ah (solid line) and E-3ah (dotted line) upon irradiation at 365 nm (LED spotlight) determined by RP-HPLC (detection at 350 nm); C) Photofatigue-resistance of 3ah upon alternating irradiation at 365 nm and 450 nm (LED spotlight) determined by RP-HPLC (detection at 350 nm).

  to ensure a high  value, as exemplified by the R 8 =CO2H case for which ∠C a C b C 7 C 6 = 41° and  = 1 nm, proving that structural and electronic effects cannot be fully disentangled.

Figure 6 .

 6 Figure 6. Calculated vertical absorption wavelengths (in nm) for the 𝑆 0 → 𝑆 1 vertical electronic transition in selected molecules. CAM-B3LYP/6-31++G(d,p) level of theory, pure DMSO is treated as an implicit solvent by the IEF-PCM model.

Figure 7 .

 7 Figure 7. Photoisomerization studies of 17. A) Relative absorption of Z-17 (-) and E-17 (---) in H2O/DMSO 1:1 (v/v) at 25 °C. B) Relative emission of Z-17 (-) and E-17 (---) ex 350 nm in H2O/DMSO 1:1 (v/v) at 25 °C; C) Time-course of photoisomerization of Z-17 upon irradiation at 300 nm (monochromator) and E-3ah upon irradiation at 450 nm (LED spotlight), determined by RP-HPLC (detection at 303 nm); D) Evolution of the absorption spectra for E-17 (in red) under irradiation at 450 nm (LED spotlight) after 1, 3, 5, 7, 10 min. (in black), and 15 min. (in blue); E) Photofatigueresistance of 17 upon alternating irradiation at 300 nm (monochromator) and 450 nm (LED spotlight), determined by RP-HPLC (detection at 303 nm).

Figure 8 .

 8 Figure 8. Calculated energy profiles () of the three lowest electronic states for the Z-E isomerization process for compound 17 as a function of intrinsic reaction coordinate  and variation of the HCCH dihedral angle (right vertical axis). CAM-B3LYP/6-31++G(d,p) level of theory, DMSO is treated as an implicit solvent by the IEF-PCM model.

Acknowledgements

The authors thank the Agence Nationale pour la Recherche (ANR-16-CE07-0004, "Click_and_Fish") for Ph.D fellowship to A.L and the University of Rouen Normandy for Ph.D fellowship to C.P. This work has also been partially supported by University of Rouen Normandy, the Centre National de la Recherche Scientifique (CNRS), INSA Rouen Normandy, European Regional Development Fund (ERDF), Labex SynOrg (ANR-11-LABX-0029), Carnot Institute I2C, the graduate school for research XL-Chem (ANR-18-EURE-0020 XL CHEM), and by Region Normandie. The Centre Régional Informatique et d'Applications Numériques de Normandie (CRIANN) is acknowledged for providing high performance computational resources. Albert Marcual (CNRS) is also acknowledge for HRMS analyses.

Metalloenzyme-Mediated Thiol-Yne Addition towards Photoisomerizable Fluorescent Dyes

A regioselective metalloenzyme-directed synthesis of a vinyl sulfide-based inhibitor, which has shown to be involved in an unexpected Z to E photoisomerization process, is reported. Tuning of the spectral features guided by theoretical studies, revealed structural modifications for effective bidirectional photoconversion of thermally bistable vinyl sulfide diastereoisomers, while maintaining high the biological activity of the parent inhibitor.