Redicolouring digraphs: directed treewidth and cycle-degeneracy
share
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. In this work, using this new definition of cycle-degeneracy, we extend several evidences for Cereceda's conjecture to digraphs. The k-dicolouring graph of D, denoted by 𝒟_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. We show that 𝒟_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.). Next, we extend a result due to Feghali to digraphs, showing that 𝒟_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 for undirected graphs can be extended to digraphs. The first one uses the digrundy number of a digraph and the second one uses the 𝒟-width. 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). This result directly extends a number of results on planar graph recolouring to planar digraph redicolouring.
READ FULL TEXT