Geodesic
Coloring squares of planar graphs with small maximum degree
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 817-835

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {44},
     number = {3},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/