Article in volume
Authors:
Title:
Coloring squares of planar graphs with small maximum degree
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 817-835
Received: 2022-06-03 , Revised: 2022-09-14 , Accepted: 2022-09-15 , Available online: 2022-09-30 , https://doi.org/10.7151/dmgt.2472
Abstract:
For a graph $G$, by $\chi_2(G)$ we denote the minimum integer $k$, such that
there is a $k$-coloring of the vertices of $G$ in which vertices at distance at
most 2 receive distinct colors. Equivalently, $\chi_2(G)$ is the chromatic number
of the square of $G$. In 1977 Wegner conjectured that if $G$ is planar and has
maximum degree $\Delta$, then $\chi_2(G) \leq 7$ if $\Delta \leq 3$,
$\chi_2(G) \leq \Delta+5$ if $4 \leq \Delta \leq 7$, and $\lfloor 3\Delta/2
\rfloor +1$ if $\Delta \geq 8$. Despite extensive work, the known upper bounds
are quite far from the conjectured ones, especially for small values of $\Delta$.
In this work we show that for every planar graph $G$ with maximum degree
$\Delta$ it holds that $\chi_2(G) \leq 3\Delta+4$. This result provides the
best known upper bound for $6 \leq \Delta \leq 14$.
Keywords:
Wegner's conjecture, coloring squares of planar graphs, discharging, graph coloring
References:
- G. Agnarsson and M.M. Halldórsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651–662.
https://doi.org/10.1137/S0895480100367950 - N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125–134.
https://doi.org/10.1007/bf01204715 - O. Amini, L. Esperet and J. van den Heuvel, A unified approach to distance-two colouring of graphs on surfaces, Combinatorica 33 (2013) 253–296.
https://doi.org/10.1007/s00493-013-2573-2 - K. Appel and W. Haken, Every planar map is four colorable. Part I: Discharging, Illinois J. Math. 21 (1977) 429–490.
https://doi.org/10.1215/ijm/1256049011 - K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part II: Reducibility, Illinois J. Math. 21 (1977) 491–567.
https://doi.org/10.1215/ijm/1256049012 - O.V. Borodin, H. Broersma, A.N. Glebov and J. van den Heuvel, Stars and bunches in planar graphs. Part II: General planar graphs and colourings, CDAM Research Report Series, LSE-CDAM-2002-05 (2002).
- N. Bousquet, L. de Meyer, Q. Deschamps and T. Pierron, Square coloring planar graphs with automatic discharging (2022).
arXiv: 2204.05791 - T. Calamoneri, The $L(h,k)$-labelling problem: An updated survey and annotated bibliography, Comput. J. 54 (2011) 1344–1371.
https://doi.org/10.1093/comjnl/bxr037 - D.W. Cranston and L. Rabern, Painting squares in $\Delta^2-1$ shades, Electron. J. Combin. 23(2) (2016) #P2.50.
https://doi.org/10.37236/4978 - Z. Dvořák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths $4$ to $8$, J. Combin. Theory Ser. B 129 (2018) 38–54.
https://doi.org/10.1016/j.jctb.2017.09.001 - Z. Dvořák, D. Král' and R. Thomas, Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies, J. Combin. Theory Ser. B 150 (2020) 244–269.
https://doi.org/10.1016/j.jctb.2020.04.006 - H. Grötzsch, Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 8 (1959) 109–120.
- J. Grytczuk and X. Zhu, The Alon-Tarsi number of a planar graph minus a matching, J. Combin. Theory, Ser. B 145 (2020) 511–520.
https://doi.org/10.1016/j.jctb.2020.02.005 - F. Havet, J. van den Heuvel, C. McDiarmid and B.A. Reed, List colouring squares of planar graphs, Electron. Notes Discrete Math. 29 (2007) 515–519.
https://doi.org/10.1016/j.endm.2007.07.079 - K. Jonas, Graph Coloring Analogues with a Condition at Distance Two: $L(2, 1)$-Labellings and List $\lambda$-Labellings, PhD Thesis (University of South Carolina, 1993).
- T. Madaras and A. Marcinová, On the structural result on normal plane maps, Discuss. Math. Graph Theory 22 (2002) 293–303.
https://doi.org/10.7151/dmgt.1176 - M. Molloy and M.R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B 94 (2005) 189–213.
https://doi.org/10.1016/j.jctb.2004.12.005 - N. Robertson, D.P. Sanders, P. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997) 2–44.
https://doi.org/10.1006/jctb.1997.1750 - C. Thomassen, Every planar graph is $5$-choosable, J. Combin. Theory Ser. B 62 (1994) 180–181.
https://doi.org/10.1006/jctb.1994.1062 - C. Thomassen, Applications of Tutte Cycles (Technical Report, Technical University of Denmark, 2001).
- J. van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110–124.
https://doi.org/10.1002/jgt.10077 - G. Wegner, Graphs with Given Diameter and a Coloring Problem (Technical Report, Technical University of Dortmund, 1977).
https://doi.org/10.17877/DE290R-16496 - S.A. Wong, Colouring Graphs with Respect to Distance, Master's Thesis (University of Waterloo, 1996).
- J. Zhu and Y. Bu, Minimum $2$-distance coloring of planar graphs and channel assignment, J. Comb. Optim. 36 (2018) 55–64.
https://doi.org/10.1007/s10878-018-0285-7
Close