2023/07/13 by Nisse, Nicolas, Picasarri-Arrieta, Lucas, Sau, Ignasi · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.06700
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 Dk(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 Dk(D) has diameter at most Oδ^*c(D)(nδ^*c(D) + 1) (respectively O(n2) and (δ^*c(D)+1)n) 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 Dd+1(D) has diameter at most Od,ε(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 \mathscrD-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.