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

DOI10.1016/J.JCTB.2018.06.005zbMATH Open1402.05043arXiv1508.03663OpenAlexW2963534041MaRDI QIDQ1633752FDOQ1633752

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)

Abstract: We prove a conjecture of Dvov{r}'ak, Kr'al, Nejedl'y, and v{S}krekovski that planar graphs of girth at least five are square $(Delta+2)$-colorable for large enough $Delta$. In fact, we prove the stronger statement that such graphs are square $(Delta+2)$-choosable and even square $(Delta+2)$-paintable.

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

Recommendations

• Plane graphs are entirely \((\Delta + 5)\)-choosable
• Acyclic 4-choosability of planar graphs with girth at least 5
• Planar graphs with girth at least 5 are \((3, 5)\)-colorable
• Total choosablility of planar graphs with maximum degree 5
• Every planar graph is 5-choosable
• A sufficient condition for planar graphs to be acyclically 5-choosable
• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• Injective choosability of planar graphs of girth five and six
• Choosability of the square of planar subcubic graphs with large girth
• Choosability and edge choosability of planar graphs without five cycles

zbMATH Keywords

choosabilityplanar graphsquarelist-coloringpaintabilitygirth 5

Mathematics Subject Classification ID

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

Cites Work

• The list chromatic index of a bipartite multigraph
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• 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
• Colorings and orientations of graphs
• List coloring the square of sparse graphs with large degree
• Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable
• List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six

Cited In (18)

• Acyclic Edge-Coloring of Planar Graphs: $\Delta$ Colors Suffice When $\Delta$ is Large
• 2-distance coloring of planar graphs without adjacent 5-cycles
• Degeneracy and colorings of squares of planar graphs without 4-cycles
• 2-Distance coloring of planar graph
• Coloring the square of maximal Planar graphs with diameter two
• Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors
• 2-distance \((\Delta + 1)\)-coloring of sparse graphs using the potential method
• The 2-distance chromatic number of planar graphs without 3,4,8-cycles
• 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles
• Graph \(r\)-hued colorings -- a survey
• 2-distance list \((\Delta +2)\)-coloring of planar graphs with girth at least 10
• List 2-distance coloring of planar graphs with girth five
• Coloring squares of planar graphs with maximum degree at most five
• Sharp upper bound of injective coloring of planar graphs with girth at least 5
• Coloring squares of planar graphs with girth six
• 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\)
• 2-Distance Coloring of Planar Graphs without 4-Cycles and 5-Cycles

This page was built for publication: Planar graphs of girth at least five are square \((\delta + 2)\)-choosable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633752)