Strengthening the Directed Brooks‘ Theorem for oriented graphs and consequences on digraph redicolouring.
EUROCOMB’23
760–765
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
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Lucas Picasarri-Arrieta