Strengthening the Directed Brooks‘ Theorem for oriented graphs and consequences on digraph redicolouring.

EUROCOMB’23

Lucas Picasarri-Arrieta

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-105

PDF
Abstract
Let $D=(V,A)$ be a digraph. We define $\Delta_{\max}(D)$ as the maximum of $\{ \max(d^+(v),d^-(v)) \mid v \in V \}$ and $\Delta_{\min}(D)$ as the maximum of $\{ \min(d^+(v),d^-(v)) \mid v \in V \}$. It is known that the dichromatic number of $D$ is at most $\Delta_{\min}(D) + 1$. In this work, we prove that every digraph $D$ which has dichromatic number exactly $\Delta_{\min}(D) + 1$ must contain the directed join of $\overleftrightarrow{K_r}$ and $\overleftrightarrow{K_s}$ for some $r,s$ such that $r+s = \Delta_{\min}(D) + 1$, except if $\Delta_{\min}(D) = 2$ in which case $D$ must contain a digon. In particular, every oriented graph $\vec{G}$ with $\Delta_{\min}(\vec{G}) \geq 2$ has dichromatic number at most $\Delta_{\min}(\vec{G})$. Let $\vec{G}$ be an oriented graph of order $n$ such that $\Delta_{\min}(\vec{G}) \leq 1$. Given two 2-dicolourings of $\vec{G}$, 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 $\vec{G}$ on $n$ vertices, the distance between two $k$-dicolourings is at most $2\Delta_{\min}(\vec{G})n$ when $k\geq \Delta_{\min}(\vec{G}) + 1$. We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph $D$ with $\Delta_{\max}(D) = \Delta \geq 3$ and every $k\geq \Delta +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(\Delta^2)$ is a constant depending only on $\Delta$.

Pages:
760–765
References

Pierre Aboulker and Guillaume Aubian. Four proofs of the directed Brooks' Theorem. arXiv preprint arXiv:2109.01600, 2021.
https://doi.org/10.1016/j.disc.2022.113193

Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, and Daniël Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1):132-143, 2014.
https://doi.org/10.1007/s10878-012-9490-y

Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215-5226, 2009. Mathematical Foundations of Computer Science (MFCS 2007).
https://doi.org/10.1016/j.tcs.2009.08.023

Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie. Short and local transformations between (∆ + 1)-colorings. arXiv preprint arXiv:2203.08885, 2022.

Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, and Amadeus Reinald. Digraph redicolouring. arXiv preprint arXiv:2301.03417, 2023.

Rowland Leonard Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194-197, 1941.
https://doi.org/10.1017/S030500410002168X

Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(5):913-919, 2008. Selected Papers from 20th British Combinatorial Conference.
https://doi.org/10.1016/j.disc.2007.07.028

Luis Cereceda, Jan Van den Heuvel, and Matthew Johnson. Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7):1593-1606, 2009.
https://doi.org/10.1016/j.ejc.2009.03.011

Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. Journal of Graph Theory, 67(1):69-82, 2011.
https://doi.org/10.1002/jgt.20514

Carl Feghali, Matthew Johnson, and Daniël Paulusma. A reconfigurations analogue of Brooks' Theorem and its consequences. Journal of Graph Theory, 83(4):340-358, 2016.
https://doi.org/10.1002/jgt.22000

Ararat Harutyunyan and Bojan Mohar. Gallai's theorem for list coloring of digraphs. SIAM Journal on Discrete Mathematics, 25(1):170-180, 2011.
https://doi.org/10.1137/100803870

Victor Neumann-Lara. The dichromatic number of a digraph. J. Combin. Theory Ser. B., 33:265-270, 1982.
https://doi.org/10.1016/0095-8956(82)90046-6

Lucas Picasarri-Arrieta. Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring. arXiv preprint arXiv:2301.04881, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-105

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Lucas Picasarri-Arrieta

PDF