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

DOI10.1016/J.JCTB.2018.06.005MaRDI QIDQ1633752zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Daniel W. Cranston, 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

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)

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.

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

Cites work

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

Cited in

(22)

• Coloring the square of maximal Planar graphs with diameter two
• \(2\)-distance coloring of planar graph
• Acyclic edge-coloring of planar graphs: \(\Delta\) colors suffice when \(\Delta\) is large
• List 2-distance coloring of planar graphs with girth five
• Coloring squares of planar graphs with maximum degree at most five
• The 2-distance chromatic number of planar graphs without 3,4,8-cycles
• Choosability of the square of a planar graph with maximum degree four
• Sharp upper bound of injective coloring of planar graphs with girth at least 5
• The square of every subcubic planar graph of girth at least 6 is 7-choosable
• \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\)
• Coloring squares of planar graphs with girth six
• 2-distance coloring of planar graphs without 4-cycles and 5-cycles
• 2-distance choosability of planar graphs with a restriction for maximum degree
• Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors
• Graph \(r\)-hued colorings -- a survey
• 2-distance coloring of planar graphs without adjacent 5-cycles
• Degeneracy and colorings of squares of planar graphs without 4-cycles
• Choosability of the square of planar subcubic graphs with large girth
• 2-distance \((\Delta + 1)\)-coloring of sparse graphs using the potential method
• 2-distance list \((\Delta +2)\)-coloring of planar graphs with girth at least 10
• 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles
• Colouring planar graphs with bounded monochromatic components

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)