Geodesic
Coloring squares of planar graphs with small maximum degree
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 817-835 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For a graph G, by χ_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, χ_2(G) is the chromatic number of the square of G. In 1977 Wegner conjectured that if G is planar and has maximum degree Δ, then χ_2(G) ≤ 7 if Δ≤ 3, χ_2(G) ≤Δ+5 if 4 ≤Δ≤ 7, and ⌊ 3Δ//2 ⌋ +1 if Δ≥ 8. Despite extensive work, the known upper bounds are quite far from the conjectured ones, especially for small values of Δ. In this work we show that for every planar graph G with maximum degree Δ it holds that χ_2(G) ≤ 3Δ+4. This result provides the best known upper bound for 6 ≤Δ≤ 14.
Keywords: Wegner's conjecture, coloring squares of planar graphs, discharging, graph coloring 
@article{DMGT_2024_44_3_a0,
     author = {Krzyzi\'nski, Mateusz and Rz\k{a}\.zewski, Pawe{\l} and Tur, Szymon},
     title = {Coloring squares of planar graphs with small maximum degree},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {817--835},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a0/}
}
TY  - JOUR
AU  - Krzyziński, Mateusz
AU  - Rzążewski, Paweł
AU  - Tur, Szymon
TI  - Coloring squares of planar graphs with small maximum degree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 817
EP  - 835
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a0/
LA  - en
ID  - DMGT_2024_44_3_a0
ER  - 
%0 Journal Article
%A Krzyziński, Mateusz
%A Rzążewski, Paweł
%A Tur, Szymon
%T Coloring squares of planar graphs with small maximum degree
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 817-835
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a0/
%G en
%F DMGT_2024_44_3_a0
Krzyziński, Mateusz; Rzążewski, Paweł; Tur, Szymon. Coloring squares of planar graphs with small maximum degree. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 817-835. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a0/

[1] 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

[2] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125–134. https://doi.org/10.1007/bf01204715

[3] 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

[4] 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

[5] 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

[6] 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).

[7] N. Bousquet, L. de Meyer, Q. Deschamps and T. Pierron, Square coloring planar graphs with automatic discharging (2022). arXiv: 2204.05791

[8] 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

[9] D.W. Cranston and L. Rabern, Painting squares in \Delta2-1 shades, Electron. J. Combin. 23(2) (2016) #P2.50. https://doi.org/10.37236/4978

[10] 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

[11] 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

[12] 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.

[13] 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

[14] 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

[15] 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).

[16] 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

[17] 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

[18] 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

[19] 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

[20] C. Thomassen, Applications of Tutte Cycles (Technical Report, Technical University of Denmark, 2001).

[21] 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

[22] G. Wegner, Graphs with Given Diameter and a Coloring Problem (Technical Report, Technical University of Dortmund, 1977). https://doi.org/10.17877/DE290R-16496

[23] S.A. Wong, Colouring Graphs with Respect to Distance, Master's Thesis (University of Waterloo, 1996).

[24] 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