Improved square coloring of planar graphs

DOI10.1016/J.DISC.2022.113288MaRDI QIDQ6386538arXivFDO

Authors Nicolas Bousquet, Quentin Deschamps, Lucas de Meyer, Théo Pierron

Publication date 23 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.113288

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

arXiv classification

math.CO

Abstract: Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $frac32Delta+1$ colors are sufficient to square color every planar graph of maximum degree $Delta$. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2Delta+7$ colors are sufficient, which improves the best known bounds when $6leqslantDeltaleqslant31$.

This page was built for publication: Improved square coloring of planar graphs

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