Planar graphs of girth at least five are square \((\delta + 2)\)-choosable

DOI10.1016/j.jctb.2018.06.005zbMath1402.05043arXiv1508.03663OpenAlexW2963534041MaRDI QIDQ1633752

Daniel W. Cranston, Marthe Bonamy, Luke Postle

Publication date: 20 December 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.03663

zbMATH Keywords

squareplanar graphchoosabilitylist-coloringpaintabilitygirth 5

Mathematics Subject Classification ID

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

Related Items

Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors ⋮ List 2-distance coloring of planar graphs with girth five ⋮ Sharp upper bound of injective coloring of planar graphs with girth at least 5 ⋮ 2-distance list \((\Delta +2)\)-coloring of planar graphs with girth at least 10 ⋮ Degeneracy and colorings of squares of planar graphs without 4-cycles ⋮ Graph \(r\)-hued colorings -- a survey ⋮ Coloring the square of maximal Planar graphs with diameter two ⋮ 2-distance coloring of planar graphs without adjacent 5-cycles ⋮ 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles ⋮ Coloring squares of planar graphs with maximum degree at most five ⋮ 2-distance choosability of planar graphs with a restriction for maximum degree ⋮ \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\) ⋮ Acyclic Edge-Coloring of Planar Graphs: $\Delta$ Colors Suffice When $\Delta$ is Large ⋮ 2-Distance Coloring of Planar Graphs without 4-Cycles and 5-Cycles ⋮ 2-Distance coloring of planar graph

Cites Work

• Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable
• List coloring the square of sparse graphs with large degree
• List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• Colorings and orientations of graphs
• The list chromatic index of a bipartite multigraph
• Coloring squares of planar graphs with girth six
• Sufficient conditions for planar graphs to be 2-distance (\(\Delta+1\))-colourable
• Labeling Planar Graphs with Conditions on Girth and Distance Two