Redicolouring digraphs: directed treewidth and cycle-degeneracy

Description

Given a digraph D = (V, A) on n vertices and a vertex v ∈ V , the cycle-degree of v is the minimum size of a set S ⊆ V (D) \ {v} intersecting every directed cycle of D containing v. From this definition of cycle-degree, we define the c-degeneracy (or cycle-degeneracy) of D, which we denote by δ * c (D). It appears to be a nice generalisation of the undirected degeneracy. For instance, the dichromatic number χ(D) of D is bounded above by δ * c (D) + 1, where χ(D) is the minimum integer k such that D admits a k-dicolouring, i.e., a partition of its vertices into k acyclic subdigraphs. In this work, using this new definition of cycle-degeneracy, we extend several evidences for Cereceda's conjecture [12] to digraphs. The k-dicolouring graph of D, denoted by D k (D), is the undirected graph whose vertices are the k-dicolourings of D and in which two k-dicolourings are adjacent if they differ on the colour of exactly one vertex. This is a generalisation of the k-colouring graph of an undirected graph G, in which the vertices are the proper k-colourings of G. We show that D k (D) has diameter at most O δ * c (D) (n δ * c (D)+1) (respectively O(n 2) and (δ * c (D) + 1)) when k is at least δ * c (D) + 2 (respectively 3 2 (δ * c (D) + 1) and 2(δ * c (D) + 1)). This improves known results on digraph redicolouring (Bousquet et al. [9]). Next, we extend a result due to Feghali [18] to digraphs, showing that D d+1 (D) has diameter at most O d,ǫ (n(log n) d−1) when D has maximum average cycle-degree at most d − ǫ. We then show that two proofs of Bonamy and Bousquet [6] for undirected graphs can be extended to digraphs. The first one uses the digrundy number of a digraph χg(D), which is the worst number of colours used in a greedy dicolouring. If k ≥ χg(D) + 1, we show that D k (D) has diameter at most 4 • χ(D) • n. The second one uses the D-width of a digraph, denoted by Dw(D), which is a generalisation of the treewidth to digraphs. If k ≥ Dw(D) + 2, we show that D k (D) has diameter at most 2(n 2 + n). Finally, we give a general theorem which makes a connection between the recolourability of a digraph D and the recolourability of its underlying graph UG(D). Assume that G is a class of undirected graphs, closed under edge-deletion and with bounded chromatic number, and let k ≥ χ(G) (i.e., k ≥ χ(G) for every G ∈ G) be such that, for every n-vertex graph G ∈ G, the diameter of the k-colouring graph of G is bounded by f (n) for some function f. We show that, for every n-vertex digraph D such that UG(D) ∈ G, the diameter of D k (D) is bounded by 2f (n). For instance, this result directly extends a number of results on planar graph recolouring to planar digraph redicolouring.

Additional details