Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring

DOI10.1002/JGT.23066arXiv2301.04881OpenAlexW4389382778MaRDI QIDQ6201022FDOQ6201022

L. Picasarri-Arrieta

Publication date: 25 March 2024

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let $D=(V,A)$ be a digraph. We define $Delt{a}_{max}(D)$ as the maximum of $max(d^{+}(v),d^{-}(v))midvinV$ and $Delt{a}_{min}(D)$ as the maximum of $min(d^{+}(v),d^{-}(v))midvinV$. It is known that the dichromatic number of $D$ is at most $Delt{a}_{min}(D)+1$. In this work, we prove that every digraph $D$ which has dichromatic number exactly $Delt{a}_{min}(D)+1$ must contain the directed join of $overleftrightarrow{K}_r$ and $overleftrightarrow{K}_s$ for some $r,s$ such that $r+s=Delt{a}_{min}(D)+1$, except if $Delt{a}_{min}(D)=2$ in which case $D$ must contain a digon. In particular, every oriented graph $vecG$ with $Delt{a}_{min}(vecG)geq2$ has dichromatic number at most $Delt{a}_{min}(vecG)$. Let $vecG$ be an oriented graph of order $n$ such that $Delt{a}_{min}(vecG)leq1$. Given two 2-dicolourings of $vecG$, we show that we can transform one into the other in at most $n$ steps, by recolouring one vertex at each step while maintaining a dicolouring at any step. Furthermore, we prove that, for every oriented graph $vecG$ on $n$ vertices, the distance between two $k$-dicolourings is at most $2Delt{a}_{min}(vecG)n$ when $kgeqDelt{a}_{min}(vecG)+1$. We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph $D$ with $Delt{a}_{max}(D)=Deltageq3$ and every $kgeqDelta+1$, the $k$-dicolouring graph of $D$ consists of isolated vertices and at most one further component that has diameter at most $c_{Delta}{n}^2$, where $c_{Delta}=O(Delt{a}^2)$ is a constant depending only on $Delta$.

Full work available at URL: https://arxiv.org/abs/2301.04881

zbMATH Keywords

directed graphsreconfigurationdichromatic numberoriented graphsgraph recolouring

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The circular chromatic number of a digraph
• Strengthened Brooks' theorem for digraphs of girth at least three
• Mixing 3-colourings in bipartite graphs
• The dichromatic number of a digraph
• The complexity of change
• Finding paths between 3-colorings
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Gallai's Theorem for List Coloring of Digraphs
• Introduction to reconfiguration
• A reconfigurations analogue of Brooks' theorem and its consequences

Cited In (1)

• Redicolouring digraphs: directed treewidth and cycle-degeneracy

This page was built for publication: Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201022)