Single-conflict colorings of degenerate graphs

EUROCOMB’23

Abstract
We consider the single-conflict coloring problem, in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex coloring such that no two adjacent vertices receive a pair of colors forbidden at an edge joining them. We show that for any assignment of forbidden color pairs to the edges of a $d$-degenerate graph $G$ on $n$ vertices of edge-multiplicity at most $\log \log n$, $O(\sqrt{ d } \log n)$ colors are always enough to color the vertices of $G$ in a way that avoids every forbidden color pair. This answers a question of Dvořák, Esperet, Kang, and Ozeki for simple graphs (Journal of Graph Theory 2021).

Pages:
201–209
References

Ron Aharoni, Eli Berger, Maria Chudnovsky, Frédéric Havet, and Zilin Jiang. Cooperative colorings of trees and bipartite graphs. Electron. J. Combin., 27(1):Paper 1.41, 2020. doi:10.37236/8111.
https://doi.org/10.37236/8111

Jurgen Aliaj and Michael Molloy. Adaptable and conflict colouring multigraphs with no cycles of length three or four, 2021. arXiv:2107.04253.

Peter Bradshaw and Tomáš Masařík. Single-conflict colorings of degenerate graphs, 2021. arXiv:2112.06333.

Zdeněk Dvořák, Louis Esperet, Ross J. Kang, and Kenta Ozeki. Single-conflict colouring. J. Graph Theory, 97(1):148-160, 2021. doi:10.1002/jgt.22646.
https://doi.org/10.1002/jgt.22646

Zdeněk Dvořák and Luke Postle. Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8. J. Combin. Theory Ser. B, 129:38-54, 2018. doi:10.1016/j.jctb.2017.09.001.
https://doi.org/10.1016/j.jctb.2017.09.001

Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In 57th Annual IEEE Symposium on Foundations of Computer Science-FOCS 2016, pages 625-634. IEEE Computer Soc., Los Alamitos, CA, 2016. doi:10.1109/FOCS. 2016.73.
https://doi.org/10.1109/FOCS.2016.73

Stefan Glock and Benny Sudakov. An average degree condition for independent transversals. J. Combin. Theory Ser. B, 154:370-391, may 2022. doi:10.1016/j. jctb.2022.01.004.
https://doi.org/10.1016/j.jctb.2022.01.004

Carla Groenland, Tomáš Kaiser, Oscar Treffers, and Matthew Wales. Graphs of low average degree without independent transversals. J. Graph Theory, 102(2):374-387, February 2023. doi:10.1002/jgt.22876.
https://doi.org/10.1002/jgt.22876

Penny E. Haxell. A note on vertex list colouring. Combin. Probab. Comput., 10(4):345-347, 2001. doi:10.1017/S0963548301004758.
https://doi.org/10.1017/S0963548301004758

Pavol Hell and Xuding Zhu. On the adaptable chromatic number of graphs. European J. Combin., 29(4):912-921, 2008. doi:10.1016/j.ejc.2007.11.015.
https://doi.org/10.1016/j.ejc.2007.11.015

Ross J Kang and Tom Kelly. Colorings, transversals, and local sparsity. Random Struct. Algorithms, 61(1):173-192, August 2022. doi:10.1002/rsa.21051.
https://doi.org/10.1002/rsa.21051

Alexandr V. Kostochka and Xuding Zhu. Adapted list coloring of graphs and hypergraphs. SIAM J. Discrete Math., 22(1):398-408, 2008. doi:10.1137/070698385.
https://doi.org/10.1137/070698385

Michael Molloy. The adaptable chromatic number and the chromatic number. J. Graph Theory, 84(1):53-56, 2017. doi:10.1002/jgt.22011.Single-conflict colorings of degenerate graphs
https://doi.org/10.1002/jgt.22011

Michael Molloy. The list chromatic number of graphs with small clique number. J. Combin. Theory Ser. B, 134:264-284, 2019. doi:10.1016/j.jctb.2018.06.007.
https://doi.org/10.1016/j.jctb.2018.06.007

Michael Molloy and Giovanna Thron. An asymptotically tight bound on the adaptable chromatic number. J. Graph Theory, 71(3):331-351, 2012. doi:10.1002/jgt.20649.
https://doi.org/10.1002/jgt.20649

Joel Spencer. Asymptotic lower bounds for Ramsey functions. 20(1):69-76, 1977/78. doi:10.1016/0012-365X(77)90044-9.
https://doi.org/10.1016/0012-365X(77)90044-9

Metrics

0

Views

0

PDF views