Lucas Picasarri-Arrieta
email: lucas.picasarri-arrieta@inria.fr

Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring *

Keywords: directed graphs, oriented graphs, dichromatic number, graph recolouring, reconfiguration

Let D = (V, A) be a digraph. We define ∆max(D) as the maximum of {max(d

It is known that the dichromatic number of D is at most ∆min(D) + 1. In this work, we prove that every digraph D which has dichromatic number exactly ∆min(D) + 1 must contain the directed join of ← → Kr and ← → Ks for some r, s such that r + s = ∆min(D) + 1, except if ∆min(D) = 2 in which case D must contain a digon. In particular, every oriented graph ⃗ G with ∆min( ⃗ G) ≥ 2 has dichromatic number at most ∆min( ⃗ G). Let ⃗ G be an oriented graph of order n such that ∆min( ⃗ G) ≤ 1. Given two 2-dicolourings of ⃗ G, we show that we can transform one into the other in at most n steps, by recolouring exactly one vertex at each step while maintaining a dicolouring at any step. Furthermore, we prove that, for every oriented graph ⃗ G on n vertices, the distance between two k-dicolourings is at most 2∆min( ⃗ G)n when k ≥ ∆min( ⃗ G) + 1. We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph D with ∆max(D) = ∆ ≥ 3 and every k ≥ ∆ + 1, the k-dicolouring graph of D consists of isolated vertices and at most one further component that has diameter at most c∆n 2 , where c∆ = O(∆ 2 ) is a constant depending only on ∆.

Introduction

Graph (re)colouring

Given a graph G = (V, E), a k-colouring of G is a function c : V -→ {1, . . . , k} such that, for every edge xy ∈ E, we have c(x) ̸ = c(y). So for every i ∈ {1, . . . , k}, c -1 (i) induces an independent set on G. The chromatic number of G, denoted by χ(G), is the smallest k such that G admits a k-colouring. The maximum degree of G, denoted by ∆(G), is the degree of the vertex with the greatest number of edges incident to it. A simple greedy procedure shows that, for any graph G, χ(G) ≤ ∆(G) + 1. The celebrated theorem of Brooks [START_REF] Leonard | On colouring the nodes of a network[END_REF] characterizes the graphs for which equality holds.

Theorem 1 (Brooks, [START_REF] Leonard | On colouring the nodes of a network[END_REF]). A connected graph G satisfies χ(G) = ∆(G) + 1 if and only if G is an odd cycle or a complete graph.

For any k ≥ χ(G), the k-colouring graph of G, denoted by C k (G), is the graph whose vertices are the kcolourings of G and in which two k-colourings are adjacent if they differ by the colour of exactly one vertex. A path (or a walk) between two given colourings α, β in C k (G) corresponds to a recolouring sequence. The existence of such a recolouring sequence witnesses the fact that β can be obtained from α by recolouring exactly one vertex at each step while maintaining a colouring at any step. If C k (G) is connected, we say that G is kmixing. A k-colouring of G is k-frozen if it is an isolated vertex in C k (G). The graph G is k-freezable if it admits a k-frozen colouring. In the last fifteen years, since the papers of Cereceda, van den Heuvel and Johnson [START_REF] Cereceda | Finding paths between 3-colorings[END_REF][START_REF] Cereceda | Mixing 3-colourings in bipartite graphs[END_REF],

Theorem 2 ( [START_REF] Feghali | A reconfigurations analogue of Brooks' Theorem and its consequences[END_REF]). Let G = (V, E) be a connected graph with ∆(G) = ∆ ≥ 3, k ≥ ∆ + 1, and α, β two k-colourings of G. Then at least one of the following holds:

• α is k-frozen, or • β is k-frozen, or
• there is a recolouring sequence of length at most c ∆ |V | 2 between α and β, where c ∆ = O(∆) is a constant depending on ∆.

Considering graphs of bounded maximum degree, Theorem 2 has been very recently improved by Bousquet, Feuilloley, Heinrich and Rabie, who proved the following. Theorem 3 ([5]). Let G = (V, E) be a connected graph with ∆(G) = ∆ ≥ 3, k ≥ ∆ + 1, and α, β two k-colourings of G. Then at least one of the following holds:

• α is k-frozen, or • β is k-frozen, or
• there is a recolouring sequence of length at most O(∆ c∆ |V |) between α and β, where c is a constant.

In this work, we are looking for extensions of Theorems 1 and 2 to the directed case.

Digraph colouring

Let D be a digraph. A digon is a pair of arcs in opposite directions between the same vertices. A simple arc is an arc which is not in a digon. For any two vertices x, y ∈ V (D), the digon {xy, yx} is denoted by [x, y]. The digon graph of D is the undirected graph with vertex set V (D) in which uv is an edge if and only if [u, v] is a digon of D. An oriented graph is a digraph with no digon. The bidirected graph associated to a graph G, denoted by ← → G , is the digraph obtained from G, by replacing every edge by a digon. The underlying graph of D, denoted by U G(D), is the undirected graph G with vertex set V (D) in which uv is an edge if and only if uv or vu is an arc of D.

Let v be a vertex of a digraph D. The out-degree (resp. in-degree) of v, denoted by

d + (v) (resp. d -(v))
, is the number of arcs leaving (resp. entering) v. We define the maximum degree of v as d max (v) = max{d + (v), d -(v)}, and the minimum degree of v as d min (v) = min{d + (v), d -(v)}. We can then define the corresponding maximum degrees of D:

∆ max (D) = max v∈V (D) (d max (v)) and ∆ min (D) = max v∈V (D) (d min (v)). A digraph D is ∆- diregular if, for every vertex v ∈ V (D), d -(v) = d + (v) = ∆.
In 1982, Neumann-Lara [START_REF] Neumann-Lara | The dichromatic number of a digraph[END_REF] introduced the notions of dicolouring and dichromatic number, which generalize the ones of colouring and chromatic number. A k-dicolouring of D is a function c : V (D) → {1, . . . , k} such that c -1 (i) induces an acyclic subdigraph in D for each i ∈ {1, . . . , k}. The dichromatic number of D, denoted by ⃗ χ(D), is the smallest k such that D admits a k-dicolouring. There is a one-to-one correspondence between the k-colourings of a graph G and the k-dicolourings of the associated bidirected graph ← → G , and in particular

χ(G) = ⃗ χ( ← → G ).
Hence every result on graph colourings can be seen as a result on dicolourings of bidirected graphs, and it is natural to study whether the result can be extended to all digraphs.

The directed version of Brooks' Theorem was first proved by Harutyunyan and Mohar in [START_REF] Harutyunyan | Gallai's theorem for list coloring of digraphs[END_REF]. Aboulker and Aubian gave four new proofs of the following theorem in [START_REF] Aboulker | Four proofs of the Directed Brooks' Theorem[END_REF].

Theorem 4 (DIRECTED BROOKS' THEOREM). Let D be a connected digraph. Then ⃗ χ(D) ≤ ∆ max (D) + 1 and equality holds if and only if one of the following occurs:

• D is a directed cycle, or • D is a bidirected odd cycle, or
• D is a bidirected complete graph (of order at least 4).

It is easy to prove, by a simple greedy procedure, that every digraph D can be dicoloured with ∆ min (D) + 1 colours. Hence, one can wonder if Brooks' Theorem can be extended to digraphs using ∆ min (D) instead of ∆ max (D). Unfortunately, Aboulker and Aubian [START_REF] Aboulker | Four proofs of the Directed Brooks' Theorem[END_REF] proved that, given a digraph D, deciding whether D is ∆ min (D)-dicolourable is NP-complete. Thus, unless P=NP, we cannot expect an easy characterization of digraphs satisfying ⃗ χ(D) = ∆ min (D) + 1. Let the maximum geometric mean of a digraph D be ∆

(D) = max{ d + (v)d -(v) | v ∈ V (D)}. By definition we have ∆ min (D) ≤ ∆(D) ≤ ∆ max (D).
Restricted to oriented graphs, Harutyunyan and Mohar [START_REF] Harutyunyan | Strengthened Brooks' theorem for digraphs of girth at least three[END_REF] have strengthened Theorem 4 by proving the following.

Theorem 5 (Harutyunyan and Mohar [START_REF] Harutyunyan | Strengthened Brooks' theorem for digraphs of girth at least three[END_REF]). There is an absolute constant ∆ 1 such that every oriented graph

⃗ G with ∆( ⃗ G) ≥ ∆ 1 has ⃗ χ( ⃗ G) ≤ (1 -e -13 ) ∆( ⃗ G).
In Section 2, we prove another strengthening of Theorem 4 on a large class of digraphs which contains oriented graphs. The directed join of H 1 and H 2 , denoted by H 1 ⇒ H 2 , is the digraph obtained from disjoint copies of H 1 and H 2 by adding all arcs from the copy of H 1 to the copy of H 2 (H 1 or H 2 may be empty). Theorem 6. Let D be a digraph. If D is not ∆ min (D)-dicolourable, then one of the following holds:

• ∆ min (D) ≤ 1, or • ∆ min (D) = 2 and D contains ← → K 2 , or • ∆ min (D) ≥ 3 and D contains ← → K r ⇒ ← → K s , for some r, s ≥ 0 such that r + s = ∆ min (D) + 1.
In particular, the following is a direct consequence of Theorem 6. vertices as a subdigraph.

Moreover, since an oriented graph does not contain any digon, Corollary 7 implies the following, which answers a question of Harutyunyan [12]:

Corollary 8. Let ⃗ G be an oriented graph. If ∆ min ( ⃗ G) ≥ 2, then ⃗ χ( ⃗ G) ≤ ∆ min ( ⃗ G).
We also show in Section 2 that Corollary 7 is best possible by showing the following.

Digraph redicolouring

For any k ≥ ⃗ χ(D), the k-dicolouring graph of D, denoted by D k (D), is the graph whose vertices are the kdicolourings of D and in which two k-dicolourings are adjacent if they differ by the colour of exactly one vertex.

Observe that C k (G) = D k ( ← → G ) for any bidirected graph ← → G . A redicolouring sequence between two dicolourings is a path between these dicolourings in D k (D). The digraph D is k-mixing if D k (D) is connected. A k-dicolouring of D is k-frozen if it is an isolated vertex in D k (D). The digraph D is k-freezable if it admits a k-frozen dicolouring.
A vertex v is blocked to its colour in a dicolouring α if, for every colour c ̸ = α(v), recolouring v to c in α creates a monochromatic directed cycle.

Digraph redicolouring was first introduced in [START_REF] Bousquet | Digraph redicolouring[END_REF], where the authors generalized different results on graph recolouring to digraphs, and proved some specific results on oriented graphs redicolouring. In particular, they studied the k-dicolouring graph of digraphs with bounded degeneracy or bounded maximum average degree, and they show that finding a redicolouring sequence between two given k-dicolourings of a digraph is PSPACE-complete. Dealing with the maximum degree of a digraph, they proved that, given an orientation of a subcubic graph ⃗ G on n vertices, its 2-dicolouring graph D 2 ( ⃗ G) is connected and has diameter at most 2n and they asked if this bound can be improved. We answer this question in Section 3 by proving the following theorem.

Theorem 10. Let ⃗ G be an oriented graph of order n such that ∆ min ( ⃗ G) ≤ 1. Then D 2 ( ⃗ G) is connected and has diameter exactly n.

In particular, if ⃗

G is an orientation of a subcubic graph, then

∆ min ( ⃗ G) ≤ 1 (because d + (v) + d -(v) ≤ 3
for every vertex v), and so D 2 ( ⃗ G) has diameter exactly n. Furthermore, we prove the following as a consequence of Corollary 8 and Theorem 10.

Corollary 11. Let ⃗ G be oriented graph of order n with ∆ min ( ⃗ G) = ∆ ≥ 1, and let k ≥ ∆ + 1. Then D k ( ⃗ G
) is connected and has diameter at most 2∆n.

Corollary 11 does not hold for digraphs in general: indeed, ← → P n , the bidirected path on n vertices, satisfies

∆ min ( ← → P n ) = 2 and D 3 ( ← → P n ) = C 3 (P n ) has diameter Ω(n 2
), as proved in [START_REF] Bonamy | Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs[END_REF]. Finally in Section 4, we extend Theorem 2 to digraphs as follows.

Theorem 12. Let D = (V, A) be a connected digraph with ∆ max (D) = ∆ ≥ 3, k ≥ ∆ + 1, and α, β two k-dicolourings of D.
Then at least one of the following holds:

• α is k-frozen, or • β is k-frozen, or
• there is a redicolouring sequence of length at most c ∆ |V | 2 between α and β, where

c ∆ = O(∆ 2 ) is a constant depending only on ∆.
Furthermore, we prove that a digraph D is k-freezable only if D is bidirected and its underlying graph is k-freezable. Thus, an obstruction in Theorem 12 is exactly the bidirected graph of an obstruction in Theorem 2.

Proofs of Theorems 6 and 9

A digraph D is k-dicritical if ⃗ χ(D) = k and for every vertex v ∈ V (D), ⃗ χ(D -v) < k.
Observe that every digraph with dichromatic number at least k contains a k-dicritical subdigraph.

Let F 2 be { ← → K 2 }, and for each ∆ ≥ 3, we define

F ∆ = { ← → K r ⇒ ← → K s | r, s ≥ 0 and r + s = ∆ + 1}. A digraph D is F ∆ -free if it
does not contain F as a subdigraph, for any F ∈ F ∆ . Theorem 6 can then be reformulated as follows:

Theorem 6. Let D be a digraph with ∆ min (D) = ∆ ≥ 2. If D is F ∆ -free, then ⃗ χ(D) ≤ ∆. Proof. Let D be a digraph such that ∆ min (D) = ∆ ≥ 2 and ⃗ χ(D) = ∆ + 1. We will show that D contains some F ∈ F ∆ as a subdigraph.
Let (X, Y ) be a partition of V (D) such that for each x ∈ X, d + (x) ≤ ∆, and for each y ∈ Y , d -(y) ≤ ∆. We define the digraph D as follows:

• V ( D) = V (D), • A( D) = A(D⟨X⟩) ∪ A(D⟨Y ⟩) ∪ {xy, yx | xy ∈ A(D), x ∈ X, y ∈ Y }. Claim 6.1: ⃗ χ( D) ≥ ∆ + 1.
Proof of claim. Assume for a contradiction that there exists a ∆-dicolouring c of D. Then D, coloured with c, must contain a monochromatic directed cycle C. Now C is not contained in X nor Y , for otherwise C would be a monochromatic directed cycle of D⟨X⟩ or D⟨Y ⟩ and so a monochromatic directed cycle of D. Thus C contains an arc xy from X to Y . But then, [x, y] is a monochromatic digon in D, a contradiction.

♢ Since ⃗ χ( D) ≥ ∆ + 1, there is a (∆ + 1)-dicritical subdigraph H of D. By dicriticality of H, for every vertex v ∈ V (H), d + H (v) ≥ ∆ and d - H (v) ≥ ∆,
for otherwise a ∆-dicolouring of H -v could be extended to H by choosing for v a colour which is not appearing in its out-neighbourhood or in its in-neighbourhood. We define X H as X ∩ V (H) and Y H as Y ∩ V (H). Note that both H⟨X H ⟩ and H⟨Y H ⟩ are subdigraphs of D. Claim 6.2: H is ∆-diregular.

Proof of claim. Let ℓ be the number of digons between X H and Y H in H. Observe that, by definition of X and H, for each vertex x ∈ X H , d + H (x) = ∆. Note also that, in H, ℓ is exactly the number of arcs leaving X H and exactly the number of arcs entering X H . We get: Proof. Let D = (V, A) be an instance of k-DICOLOURABILITY for some fixed k ≥ 2. Then we build D ′ = (V ′ , A ′ ) as follows:

∆|X H | = x∈X H d + H (x) = ℓ + |A(H⟨X H ⟩)| = x∈X H d - H (x) which implies, since H is dicritical, d + H (x) = d - H (x) = ∆ for every vertex x ∈ X H . Using a symmetric argument, we prove that ∆|Y H | = y∈Y H d + H (y), implying d + H (y) = d - H (y) = ∆ for every vertex y ∈ Y H . ♢ Since H is ∆-diregular, then in particular ∆ max (H) = ∆. Hence, because ⃗ χ(H) = ∆ + 1,
• For each vertex x ∈ V , we associate a copy of S -

x ⇒ S + x where S - x is the bidirected complete graph on k+1 2

vertices, and S + x is the bidirected complete graph on k+1 2 vertices.

• For each arc xy ∈ A, we associate all possible arcs x + y -in A ′ , such that x + ∈ S + x and y -∈ S - y .

First observe that ∆ min (D ′ ) = k. Let v be a vertex of D ′ , if v belongs to some S + x , then d -(v) = k, otherwise it belongs to some S -

x and then d + (v) = k. Then observe that D ′ does not contain the bidirected complete graph on k+1 2 + 1 vertices since every digon in D ′ is contained in some S +

x or S - x . Thus we only have to prove that

⃗ χ(D) ≤ k if and only if ⃗ χ(D ′ ) ≤ k to get the result. • Let us first prove that ⃗ χ(D) ≤ k implies ⃗ χ(D ′ ) ≤ k. Assume that ⃗ χ(D) ≤ k. Let ϕ : V - → {1, .
. . , k} be a k-dicolouring of D. Let ϕ ′ be the k-dicolouring of D ′ defined as follows: for each vertex x ∈ V , choose arbitrarily x -∈ S -

x , x + ∈ S + x , and set ϕ ′ (x -) = ϕ ′ (x + ) = ϕ(x). Then choose a distinct colour for every other vertex v in S -

x ∪ S + x , and set ϕ ′ (v) to this colour. We get that ϕ ′ must be a k-dicolouring of D ′ : for each x ∈ V , every vertex but x -in S - x must be a sink in its colour class, and every vertex but x + in S +

x must be a source in its colour class. Thus if D ′ , coloured with ϕ ′ , contains a monochromatic directed cycle C ′ , then C ′ must be of the form

x - 1 x + 1 x - 2 x + 2 • • • x - ℓ x + ℓ x - 1 . But then C = x 1 x 2 • • • x ℓ x 1 is a monochromatic directed cycle in D coloured with ϕ: a contradiction. • Reciprocally, let us prove that ⃗ χ(D ′ ) ≤ k implies ⃗ χ(D) ≤ k. Assume that ⃗ χ(D ′ ) ≤ k. Let ϕ ′ : V ′ - → {1, . . . , k} be a k-dicolouring of D ′ .
Let ϕ be the k-dicolouring of D defined as follows. For each vertex x ∈ V , we know that |S +

x ∪ S - x | = k + 1, thus there must be two vertices x + and x -in S +

x ∪ S - x such that ϕ ′ (x + ) = ϕ ′ (x -). Moreover, since both S + x and S - x are bidirected, one of these two vertices belongs to S +

x and the other one belongs to S - x . We assume without loss of generality x + ∈ S +

x and x -∈ S - x . Then we set ϕ(x) = ϕ ′ (x + ). We get that ϕ must be a k-

dicolouring of D. If D, coloured with ϕ, contains a monochromatic directed cycle C = x 1 x 2 • • • x ℓ x 1 , then C ′ = x - 1 x + 1 x - 2 x + 2 • • • x - ℓ x + ℓ x - 1 is a monochromatic directed cycle in D ′ coloured with ϕ ′ , a contradiction.
3 Proofs of Theorem 10 and Corollary 11

In this section, we restrict to oriented graphs. We first prove Theorem 10, let us restate it.

Theorem 10. Let ⃗ G be an oriented graph of order n such that ∆ min ( ⃗ G) ≤ 1. Then D 2 ( ⃗ G) is connected and has diameter exactly n.

Observe that, if D 2 ( ⃗ G) is connected, then its diameter must be at least n: for any 2-dicolouring α, we can define its mirror ᾱ where, for every vertex v ∈ V ( ⃗ G), α(v) ̸ = ᾱ(v); then every redicolouring sequence between α and ᾱ has length at least n. Lemma 14. Let C be a directed cycle of length at least 3. Then D 2 (C) is connected and has diameter exactly n.

Proof. Let α and β be any two 2-dicolourings of

C. Let x = diff(α, β) = |{v ∈ V (C) | α(v) ̸ = β(v)}|.
By induction on x ≥ 0, let us show that there exists a path of length at most x from α to β in D 2 (C). This clearly holds for x = 0 (i.e., α = β). Assume x > 0 and the result holds for x -1. Let v ∈ V (C) be such that α(v) ̸ = β(v).

If v can be recoloured in β(v), then we recolour it and reach a new 2-dicolouring α ′ such that diff(α ′ , β) = x-1 and the result holds by induction. Else if v cannot be recoloured, then recolouring v must create a monochromatic directed cycle, which must be C. Then there must be a vertex v ′ , different from v, such that β(v) = α(v ′ ) ̸ = β(v ′ ), and v ′ can be recoloured. We recolour it and reach a new 2-dicolouring α ′ such that diff(α ′ , β) = x -1. The result then holds by induction.

We are now ready to prove Theorem 10.

Proof of Theorem 10. Let α and β be any two 2-dicolourings of ⃗ G. We will show that there exists a redicolouring sequence of length at most n between α and β. We may assume that ⃗ G is strongly connected, otherwise we consider each strongly connected component independently. This implies in particular that ⃗ G does not contain any sink nor source. Let (X, Y ) be a partition of V ( ⃗ G) such that, for every x ∈ X, d + (x) = 1, and for every y ∈ Y , d -(y) = 1.

Assume first that ⃗ G⟨X⟩ contains a directed cycle C. Since every vertex in X has exactly one out-neighbour, there is no arc leaving C. Thus, since ⃗ G is strongly connected, ⃗ G must be exactly C, and the result holds by Lemma 14. Using a symmetric argument, we get the result when ⃗ G⟨Y ⟩ contains a directed cycle. Assume now that both ⃗ G⟨X⟩ and ⃗ G⟨Y ⟩ are acyclic. Thus, since every vertex in X has exactly one outneighbour, ⃗ G⟨X⟩ is the union of disjoint and independent in-trees, that are oriented trees in which all arcs are directed towards the root. We denote by X r the set of roots of these in-trees. Symmetrically, ⃗ G⟨Y ⟩ is the union of disjoint and independent out-trees (oriented trees in which all arcs are directed away from the root), and we denote by Y r the set of roots of these out-trees. Set X ℓ = X \ X r and Y ℓ = Y \ Y r . Observe that the arcs from X to Y form a perfect matching directed from X r to Y r . We denote by M r this perfect matching. Observe also that there can be any arc from Y to X. Now we define X 1 r and Y 1 r two subsets of X r and Y r respectively, depending on the two 2-dicolourings α and β, as follows:

X 1 r = {x | xy ∈ M r , α(x) = β(y) ̸ = α(y) = β(x)} Y 1 r = {y | xy ∈ M r , α(x) = β(y) ̸ = α(y) = β(x)} Set X 2 r = X r \ X 1 r and Y 2 r = Y r \ Y 1 r . We denote by M 1 r (respectively M 2 r ) the perfect matching from X 1 r to Y 1 r (respectively from X 2 r to Y 2 r ). Figure 1 shows a partitioning of V ( ⃗ G) into X 1 r , X 2 r , X ℓ , Y 1 r , Y 2 r , Y ℓ . X 1 r X 2 r X ℓ Y 1 r Y 2 r Y ℓ ⃗ G dicoloured with α X 1 r X 2 r X ℓ Y 1 r Y 2 r Y ℓ ⃗ G dicoloured with β Figure 1: The partitioning of V ( ⃗ G) into X 1 r , X 2 r , X ℓ , Y 1 r , Y 2 r , Y ℓ .
Claim 10.1: There exists a redicolouring sequence of length s α from α to some 2-dicolouring α ′ and a redicolouring sequence of length s β from β to some 2-dicolouring β ′ such that each of the following holds:

(i) For any arc xy ∈ M r , α ′ (x) ̸ = α ′ (y) and β ′ (x) ̸ = β ′ (y),

(ii) For any arc xy ∈ M 2 r , α ′ (x) = β ′ (x) (and so α ′ (y) = β ′ (y) by (i)), and

(iii) s α + s β ≤ |X 2 r | + |Y 2 r |.
Proof of claim. We consider the arcs xy of M 2 r one after another and do the following recolourings depending on the colours of x and y in both α and β to get α ′ and β ′ .

• If α(x) = α(y) = β(x) = β(y), then we recolour x in both α and β;

• Else if α(x) = α(y) ̸ = β(x) = β(y), then we recolour x in α and we recolour y in β;

• Else if α(x) = β(x) ̸ = α(y) = β(y), then we do nothing; • Else if α(x) ̸ = α(y) = β(x) = β(y), then we recolour x in β; • Finally if α(y) ̸ = α(x) = β(x) = β(y), then we recolour y in β.
v ∈ H, we can recolour each vertex in J to its colour in γ. This shows that there is a redicolouring sequence between α and γ of length at most |V (H)| + |J| = |V ( ⃗ G)|. This ends the case ∆ = 1. Assume now that ∆ ≥ 2 and let k ≥ ∆ + 1. Let α and β be two k-dicolourings of ⃗ G. By Corollary 8, we know that ⃗ χ( ⃗ G) ≤ ∆ ≤ k -1. We first show that there is a redicolouring sequence of length at most 2n from α to some (k -1)-dicolouring γ of ⃗ G. From α, whenever it is possible we recolour each vertex coloured 1, 2 or k with a colour of {3, . . . , k -1} (when k = 3 we do nothing). Let α be the obtained dicolouring, and let M be the set of vertices coloured in {3, . . . , k -1} by α (when k = 3, M is empty). We get that H = ⃗ G -M satisfies ∆ min (H) ≤ 2, since every vertex in H has at least one in-neighbour and one out-neighbour coloured c for every c ∈ {3, . . . , k -1}. By Corollary 8, there exists a 2-dicolouring γ |H of H. From α|H , whenever it is possible, we recolour a vertex coloured 1 or 2 to colour k. Let α be the resulting dicolouring, and Ĥ be the subdigraph of H induced by the vertices coloured 1 or 2 in α. We get that ∆ min ( Ĥ) ≤ 1 since every vertex in Ĥ has, in ⃗ G, at least one in-neighbour and one out-neighbour coloured c for every c ∈ {3, . . . , k}. In at most |V ( Ĥ)| steps, using Theorem 10, we can recolour the vertices of V ( Ĥ) to their colour in γ |H (using only colours 1 and 2). Then we can recolour each vertex coloured k to its colour in γ |H . This results in a redicolouring sequence of length at most 2n from α to some (k -1)-dicolouring γ of ⃗ G , since colour k is not used in the resulting dicolouring (recall that M is coloured with {3, . . . , k -1}). Now, from β, whenever it is possible we recolour each vertex to colour k. Let β be the obtained k-dicolouring, and let N be the set of vertices coloured k in β. We get that J = ⃗ G -N satisfies ∆ min (J) ≤ ∆ -1. Thus, by induction, there exists a redicolouring sequence from β|J to γ |J , in at most 2(∆ -1)|V (J)| steps (using only colours {1, . . . , k -1}). Since N is coloured k in β, this extends to a redicolouring sequence in ⃗ G. Now, since γ does not use colour k, we can recolour each vertex in N to its colour in γ. We finally get a redicolouring sequence from β to γ of length at most 2(∆ -1)n. Concatenating the redicolouring sequence from α to γ and the one from γ to β, we get a redicolouring sequence from α to β in at most 2∆n steps.

Proof of Theorem 12

Let us restate Theorem 12.

Theorem 12. Let D be a connected digraph with ∆ max (D) = ∆ ≥ 3, k ≥ ∆ + 1, and α, β two k-dicolourings of D. Then at least one of the following holds:

• α is k-frozen, or • β is k-frozen, or
• there is a redicolouring sequence of length at most c ∆ |V | 2 between α and β, where c ∆ = O(∆ 2 ) is a constant depending only on ∆.

An L-assignment of a digraph D is a function which associates to every vertex a list of colours. An Ldicolouring of D is a dicolouring α where, for every vertex v of D, α(v) ∈ L(v). An L-redicolouring sequence is a redicolouring sequence γ 1 , . . . , γ r , such that for every i ∈ {1, . . . , r}, γ i is an L-dicolouring of D.

Lemma 15. Let D = (V, A) be a digraph and L be a list-assignment of D such that, for every vertex

v ∈ V , |L(v)| ≥ d max (v) + 1. Let α be an L-dicolouring of D. If u ∈ V is blocked in α, then for each colour c ∈ L(u) different from α(u), u has exactly one out-neighbour u + c and one in-neighbour u - c coloured c. Moreover, if u + c ̸ = u - c
, there must be a monochromatic directed path from u + c to u - c . In particular, u is not incident to a monochromatic arc.

Proof. Let x = diff(α, β) = |{v ∈ V | α(v) ̸ = β(v)}|.
We will show by induction on x that there is an Lredicolouring sequence from α to β of length at most (|V | + 3)x. The result clearly holds for x = 0 (i.e. α = β). Let v ∈ V be such that α(v) ̸ = β(v). We denote α(v) by c and β(v) by c ′ . If v can be recoloured to c ′ , then we recolour it and we get the result by induction.

Assume now that v cannot be recoloured to c ′ . Whenever v is contained in a directed cycle C of length at least 3, such that every vertex of C but v is coloured c ′ , we do the following: we choose w a vertex of C different from v, such that β(w) ̸ = c ′ . We know that such a w exists, for otherwise C would be a monochromatic directed cycle in β. Now, since w is incident to a monochromatic arc in C, and because |L(w)| ≥ d max (w) + 1, by Lemma 15, we know that w can be recoloured to some colour different from c ′ . Thus we recolour w to this colour. Observe that it does not increase x.

After repeating this process, maybe v cannot be recoloured to c ′ because it is adjacent by a digon to some vertices coloured c ′ . We know that these vertices are not coloured c ′ in β. Thus, whenever such a vertex can be recoloured, we recolour it. After this, let η be the obtained dicolouring. If v can be recoloured to c ′ in η, we are done. Otherwise, there must be some vertices, blocked to colour c ′ in η, adjacent to v by a digon. Let S be the set of such vertices. Observe that, by Lemma 15, for every vertex s ∈ S, c belongs to L(s), for otherwise s would not be blocked in η. We distinguish two cases, depending on the size of S.

• If |S| ≥ 2, then by Lemma 15, v can be recoloured to a colour c ′′ , different from both c and c ′ , because v is adjacent by a digon with two neighbours coloured c ′ . Hence we can successively recolour v to c ′′ , and every vertex of S to c . This does not create any monochromatic directed cycle because for each s ∈ S, since s is blocked in η, by Lemma 15 v must be the only neighbour of s coloured c in η.

We can finally recolour v to c ′ .

• If |S| = 1, let w be the only vertex in S. If v can be recoloured to any colour (different from c ′ since w is coloured c ′ ), then we first recolour v, allowing us to recolour w to c, because v is the single neighbour of w coloured c in η by Lemma 15. We finally can recolour v to c ′ .

Assume then that v is blocked to colour c in η. Let us fix w + ∈ N + (w) \ N -(w). Since w is blocked to c ′ in η, by Lemma 15, there exists exactly one vertex w -∈ N -(w) \ N + (w) such that η(w + ) = η(w -) = c ′′ and there must be a monochromatic directed path from w + to w -.

Since v is blocked to colour c in η, either vw -/ ∈ A or w + v / ∈ A, otherwise, by Lemma 15, there must be a monochromatic directed path from w -to w + , which is blocking v to its colour. But since there is also a monochromatic directed path from w + to w -(blocking w) there would be a monochromatic directed cycle, a contradiction (see Figure 2). We distinguish the two possible cases:

-If v i is not adjacent to y -, then we recolour y -to any possible colour, and we recolour y to η i (y -).

We can finally recolour v i to c ′ to reach the desired γ i+1 .

-Finally if v i is adjacent to both y + and y -, since η i (y + ) = η i (y -), then v i can be recoloured to a colour c ′′ different from c and c ′ . This allows us to recolour y to c, and we finally can recolour v i to c ′ to reach the desired γ i+1 .

We have shown that there is a redicolouring sequence of length at most (∆ + 2)c ∆ n 2 from α to some α ′ that agrees with β on X. Now we define the list-assignment: for each y ∈ Y ,

L(y) = {1, . . . , k} \ {β(x) | x ∈ N (y) ∩ X}.
Observe that, for every y ∈ Y , If D is not bidirected, then we choose v a vertex incident to a simple arc. If v cannot be recoloured in α, by Lemma 15, since v is incident to a simple arc, there exists a colour c for which v has an out-neighbour w and an in-neighbour u both coloured c, such that u ̸ = w and there is a monochromatic directed path from w to u. But then, every vertex on this path is incident to a monochromatic arc, and it can be recoloured by Lemma 15. Thus, α is not k-frozen. This shows that an obstruction of Theorem 12 is exactly the bidirected graph of an obstruction of Theorem 2.

|L(y)| ≥ k -|N + (y) ∩ X| ≥ ∆ + 1 -(∆ -d + Y (y)) ≥ d + Y (y) + 1.

Further research

In this paper, we established some analogues of Brooks' Theorem for the dichromatic number of oriented graphs and for digraph redicolouring. Many open questions arise, we detail a few of them.

Restricted to oriented graphs, Erdős and Neumann-Lara (see [START_REF] Erdos | Problems and results in number theory and graph theory[END_REF]) conjectured that the Directed Brooks' Theorem can be improved to the following. Concerning digraph redicolouring, we believe that Corollary 11 and Theorem 12 can be improved. We pose the following conjecture. It would also be nice to extend Theorem 3 to directed graphs, that is to show that the diameter of D k (D) is bounded by f (∆ max (D))n for some computable function f whenever k ≥ ∆ max (D) + 1 ≥ 4. To prove it, it would be sufficient to show the analogue of Lemma 16 with an L-redicolouring sequence of length at most f (∆ max (D))|V |, and then follow the proof of Theorem 12 (using Theorem 3 instead of Theorem 2).

Given an orientation ⃗

G of a planar graph, a celebrated conjecture from Neumann-Lara [START_REF] Neumann-Lara | The dichromatic number of a digraph[END_REF] states that the dichromatic number of ⃗ G is at most 2. It is known that it must be 4-mixing because planar graphs are 5degenerate [START_REF] Bousquet | Digraph redicolouring[END_REF]. It is also known that there exists 2-freezable orientations of planar graphs [START_REF] Bousquet | Digraph redicolouring[END_REF]. Thus the following problem, stated in [START_REF] Bousquet | Digraph redicolouring[END_REF], remains open: Question 21. Is every oriented planar graph 3-mixing ?

Corollary 7 .

 7 Let D be a digraph. If ⃗ χ(D) = ∆ min (D) + 1, then D contains the complete bidirected graph on ∆min+1 2

Theorem 9 . 2 + 1

 921 For every fixed k ≥ 2, k-DICOLOURABILITY remains NP-complete when restricted to digraphs D satisfying ∆ min (D) = k and not containing the bidirected complete graph on k+1 vertices.

2 + 1 2 + 1

 2121 vertices, deciding if it is ∆ min (D)-dicolourable is NP-complete. We shall use a reduction from k-DICOLOURABILITY which is defined as follows: k-DICOLOURABILITY Input: A digraph D Question: Is D k-dicolourable ? k-DICOLOURABILITY is NP-complete for every fixed k ≥ 2 [3]. It remains NP-complete when we restrict to digraphs D with ∆ min (D) = k [1]. Theorem 9. For all k ≥ 2, k-DICOLOURABILITY remains NP-complete when restricted to digraphs D satisfying ∆ min (D) = k and not containing the bidirected complete graph on k+1 vertices.

Proof.

  Since u is blocked to its colour in α, for each colour c ∈ L(u) different from α(u), recolouring u to c must create a monochromatic directed cycle C. Let v be the out-neighbour of u in C and w be the in-neighbour of u in C. Then α(v) = α(w) = c, and there is a monochromatic directed path (in C) from v to w.This implies that, for each colour c ∈ L(u) different from α(u), u has at least one out-neighbour and at least one in-neighbour coloured c. Since |L(u)| ≥ d max (u) + 1, then |L(u)| = d max (u) + 1, and u must have exactly one out-neighbour and exactly one in-neighbour coloured c. In particular, u cannot be incident to a monochromatic arc.Lemma 16. Let D = (V, A) be a digraph such that for every vertex v ∈ V , N + (v) \ N -(v) ̸ = ∅ and N -(v) \ N + (v) ̸ = ∅. Let L be a list assignment of D, such that for every vertex v ∈ V , |L(v)| ≥ d max (v) + 1.Then for any pair of L-dicolourings α, β of D, there is an L-redicolouring sequence of length at most (|V | + 3)|V |.

Figure 2 :

 2 Figure 2: The vertices v, w, w + and w -.

Remark 17 .

 17 Symmetrically, we get |L(y)| ≥ d - Y (y) + 1. This implies, in D⟨Y ⟩, |L(y)| ≥ d max (y) + 1. Note also that both α ′ |D⟨Y ⟩ and β |D⟨Y ⟩ are L-dicolourings of D⟨Y ⟩. Note finally that, for each y ∈ Y , N + (y) \ N -(y) ̸ = ∅ and N + (y) \ N -(y) ̸ = ∅ by choice of X and Y and by the initial observation. By Lemma 16, there is an Lredicolouring sequence in D⟨Y ⟩ between α ′ |D⟨Y ⟩ and β |D⟨Y ⟩ , with length at most (|Y | + 3)|Y |. By choice of L, this extends directly to a redicolouring sequence from α ′ to β on D of the same length. The concatenation of the redicolouring sequence from α to α ′ and the one from α ′ to β leads to a redicolouring sequence from α to β of length at most c ′ ∆ |V | 2 , where c ′ ∆ = O(∆ 2 ) is a constant depending on ∆. If α is a k-frozen dicolouring of a digraph D, with k ≥ ∆ max (D) + 1, then D must be bidirected.

Conjecture 18 (

 18 Erdős and Neumann-Lara). Every oriented graph⃗ G has ⃗ χ( ⃗ G) = O ∆max log(∆max) .

Conjecture 19 .

 19 There is an absolute constant c such that for every integer k and every oriented graph⃗ G on n vertices, such that k ≥ ∆ min ( ⃗ G) + 1, the diameter of D k ( ⃗ G) is bounded by cn.Conjecture 20. There is an absolute constant d such that for every integer k and every digraph D on n vertices, with k ≥ ∆ max (D) + 1 ≥ 4, the diameter of D k (D) is bounded by dn 2 .

  by Theorem 4, either ∆ = 2 and H is a bidirected odd cycle, or ∆ ≥ 3 and H is the bidirected complete graph on ∆ + 1 vertices.

• If ∆ = 2 and H is a bidirected odd cycle, then at least one digon of H belongs to H⟨X H ⟩ or H⟨Y H ⟩, for otherwise H would be bipartite (with bipartition (X H , Y H )). Since both H⟨X H ⟩ and H⟨Y H ⟩ are subdigraphs of D, this shows, as desired, that D contains a copy of ← → K 2 .

• If k ≥ 3 and H is the bidirected complete graph on ∆ + 1 vertices, let A H be all the arcs from Y H to X H . Then D⟨V (H)⟩ \ A H is a subdigraph of D which belongs to F ∆ . Now we will justify that Corollary 7 is best possible. To do so, we prove that given a digraph D which does not contain the bidirected complete graph on ∆min(D)+1

Acknowledgement

I am grateful to Frédéric Havet and Nicolas Nisse for stimulating discussions.

* Research supported by research grant DIGRAPHS ANR-19-CE48-0013 and by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE-0004.

1 researchers in graph theory. We refer the reader to the PhD thesis of Bartier [2] for a complete overview on graph recolouring and to the surveys of van Heuvel [

Each of these recolourings is valid because, when a vertex in X 2 r (respectively Y 2 r ) is recoloured, it gets a colour different from its only out-neighbour (respectively in-neighbour). Let α ′ and β ′ be the the two resulting 2dicolourings. By construction, α ′ and β ′ agree on X 2 r ∪ Y 2 r . For each arc xy ∈ M 2 r , either α(x) = α ′ (x) or α(y) = α ′ (y), and the same holds for β and β ′ . This implies that s

Claim 10.2: There exists a redicolouring sequence from α ′ to some 2-dicolouring α of length s ′ α and a redicolouring sequence from β ′ to some 2-dicolouring β of length s ′ β such that each of the following holds:

(i) α and β agree on

(ii) α ′ and α agree on X r ∪ Y r , (iii) β ′ and β agree on X r ∪ Y r , (iv) X ℓ ∪ Y ℓ is monochromatic in α (and in β by (i)), and

Proof of claim. Observe that in both 2-dicolourings α ′ and β ′ , we are free to recolour any vertex of X ℓ ∪ Y ℓ since there is no monochromatic arc from X to Y and both ⃗ G⟨X⟩ and ⃗ G⟨Y ⟩ are acyclic. Let n 1 (respectively n 2 ) be the number of vertices in X ℓ ∪ Y ℓ that are coloured 1 (respectively 2) in both α ′ and β ′ . Without loss of generality, assume that n 1 ≤ n 2 . Then we set each vertex of X ℓ ∪ Y ℓ to colour 2 in both α ′ and β ′ . Let α and β the resulting

There is a redicolouring sequence between α and β of length

By construction of α and β, we only have to exchange the colours of x and y for each arc xy ∈ M 1 r . Without loss of generality, we may assume that the colour of all vertices in X ℓ ∪ Y ℓ by α and β is 1.

We first prove that, by construction, we can recolour any vertex of X 1 r ∪Y 1 r from 1 to 2. Assume not, then there is such a vertex x ∈ X 1 r ∪ Y 1 r such that recolouring x from 1 to 2 creates a monochromatic directed cycle C. Since both ⃗ G⟨X⟩ and ⃗ G⟨Y ⟩ are acyclic, C must contain an arc of M r . Since M r does not contain any monochromatic arc in α, then this arc must be incident to x. Now observe that colour 2, in α, induces an independent set on both ⃗ G⟨X⟩ and ⃗ G⟨Y ⟩. This implies that C must contain at least 2 arcs in M r . This is a contradiction since recolouring x creates exactly one monochromatic arc in M r .

Then, for each arc xy ∈ M 1 r , we can first recolour the vertex coloured 1 and then the vertex coloured 2. Note that we maintain the invariant that colour 2 induces an independent set on both ⃗ G⟨X⟩ and ⃗ G⟨Y ⟩. We get a redicolouring sequence from α to β in exactly

Combining the three claims, we finally proved that there exists a redicolouring sequence between α and β of length at most n.

In the following, when α is a dicolouring of a digraph D, and H is a subdigraph of D, we denote by α |H the restriction of α to H. We will now prove Corollary 11, let us restate it first. Proof. We will show the result by induction on ∆.

Assume first that ∆ = 1, let k ≥ 2. Let α be any k-dicolouring of ⃗ G and γ be any 2-dicolouring of ⃗ G. To ensure that D k ( ⃗ G) is connected and has diameter at most 2n, it is sufficient to prove that there is a redicolouring sequence between α and γ of length at most n. Let H be the digraph induced by the set of vertices coloured 1 or 2 in α, and let J be V ( ⃗ G) \ V (H). By Theorem 10, since ∆ min (H) ≤ ∆ min ( ⃗ G) ≤ 1, we know that there exists a redicolouring sequence, in H, from α |H to γ |H of length at most |V (H)|. This redicolouring sequence extends in ⃗ G because it only uses colours 1 and 2. Let α ′ be the obtained dicolouring of ⃗ G. Since α ′ (v) = γ(v) for every if vw -/ ∈ A, then we start by recolouring w -with a colour that does not appear in its in-neighbourhood. This is possible because w -has a monochromatic entering arc, and because |L(w -)| ≥ d max (w -)+1. We first recolour w with c ′′ , since c ′′ does not appear in its in-neighbourhood anymore (w -was the only one by Lemma 15). Next we recolour v with c ′ : this is possible because v does not have any out-neighbour coloured c ′ since w was the only one by Lemma 15 and w -is not an out-neighbour of v. We can finally recolour w to colour c and w -to c ′′ . After all these operations, we exchanged the colours of v and w.

if w + v / ∈ A, then we use a symmetric argument.

Observe that we found an L-redicolouring sequence from α to a α ′ , in at most |V |+3 steps, such that diff(α ′ , β) < diff(α, β). Thus by induction, we get an L-redicolouring sequence of length at most (|V | + 3)x between α and β.

We are now able to prove Theorem 12. The idea of the proof is to divide the digraph D into two parts. One of them is bidirected and we will use Theorem 2 as a black box on it. In the other part, we know that each vertex is incident to at least two simple arcs, one leaving and one entering, and we will use Lemma 16 on it.

Proof of Theorem 12. Let D = (V, A) be a connected digraph with ∆ max (D) = ∆, k ≥ ∆ + 1. Let α and β be two k-dicolourings of D. Assume that neither α nor β is k-frozen.

We first make a simple observation. For any simple arc xy ∈ A, we may assume that N + (y) \ N -(y) ̸ = ∅ and N -(x) \ N + (x) ̸ = ∅. If this is not the case, then every directed cycle containing xy must contain a digon, implying that the k-dicolouring graph of D is also the k-dicolouring graph of D \ {xy}. Then we may look for a redicolouring sequence in D \ {xy}.

Observe that D⟨X⟩ is bidirected, and thus the dicolourings of D⟨X⟩ are exactly the colourings of U G(D⟨X⟩). We first show that α |D⟨X⟩ and β |D⟨X⟩ are not frozen k-colourings of D⟨X⟩. If Y is empty, then D⟨X⟩ = D and α |D⟨X⟩ and β |D⟨X⟩ are not k-frozen by assumption. Otherwise, since D is connected, there exists x ∈ X such that, in D⟨X⟩, d

implying that x is not blocked in any dicolouring of D⟨X⟩. Thus, by Theorem 2, there is a redicolouring sequence γ ′ 1 , . . . , γ ′ r in D⟨X⟩ from α |D⟨X⟩ to β |D⟨X⟩ , where r ≤ c ∆ |X| 2 , and c ∆ = O(∆) is a constant depending on ∆. We will show that, for each i ∈ {1, . . . , r -1}, if γ i is a k-dicolouring of D which agrees with γ ′ i on X, then there exist a k-dicolouring γ i+1 of D that agrees with γ ′ i+1 on X and a redicolouring sequence from γ i to γ i+1 of length at most ∆ + 2.

Observe that α agrees with γ ′ 1 on X. Now assume that there is such a γ i , which agrees with γ ′ i on X, and let v i ∈ X be the vertex for which γ ′ i (v i ) ̸ = γ ′ i+1 (v i ). We denote by c (respectively c ′ ) the colour of v i in γ ′ i (respectively γ ′ i+1 ). If recolouring v i to c ′ in γ i is valid then we have the desired γ i+1 . Otherwise, we know that v i is adjacent with a digon (since v i is only adjacent to digons) to some vertices (at most ∆) coloured c ′ in Y . Whenever such a vertex can be recoloured to a colour different from c ′ , we recolour it. Let η i be the reached k-dicolouring after these operations. If v i can be recoloured to c ′ in η i we are done. If not, then the neighbours of v i coloured c ′ in Y are blocked to colour c ′ in η i . We denote by S the set of these neighbours. We distinguish two cases:

• If |S| ≥ 2, then by Lemma 15, v i can be recoloured to a colour c ′′ , different from both c and c ′ , because v i has two neighbours with the same colour. Then we successively recolour v i to c ′′ , and every vertex of S to c. This does not create any monochromatic directed cycle because, by Lemma 15, for each s ∈ S, v i is the only neighbour of s coloured c in η i . We can finally recolour v i to c ′ to reach the desired γ i+1 .

• If |S| = 1, let y be the only vertex in S. Since y belongs to Y and is blocked to its colour in η i , by Lemma 15, we know that y has an out-neighbour y + ∈ N + (y)\N -(y) and an in-neighbour y -∈ N -(y)\N + (y) such that there is a monochromatic directed path from y + to y -. Observe that both y + and y -are recolourable in η i by Lemma 15, because there are incident to a monochromatic arc.

-If v i is not adjacent to y + , then we recolour y + to any possible colour, and we recolour y to η i (y + ). We can finally recolour v i to c ′ to reach the desired γ i+1 .