2-Distance Coloring of Planar Graphs without 4-Cycles and 5-Cycles
Wei Dong, Baogang Xu · SIAM Journal on Discrete Mathematics · 2019
A vertex coloring is said to be 2-distance if any two distinct vertices of distance at most 2 get different colors. Let $G$ be a planar graph without 4-cycles and 5-cycles. Cranston and Jaeger proved that $G$ is 2-distance $(\Delta(G)+3)$-list colorable if $\Delta(G)\ge 32$. We show that $G$ is 2-distance $(\Delta(G)+2)$-colorable if $\Delta(G)\ge 185760$. The bound $\Delta(G)+2$ is sharp as there exist non-2-distance $(k+1)$-colorable planar graphs of girth 6 and maximum degree $k$ for every integer $k\ge 2$, and there exist non-2-distance $(\Delta(G)+2)$-colorable planar graphs $G$ without 4-cycles or without 5-cycles.