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

choosabilitygirth 5list-coloringpaintabilityplanar graphsquare

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) 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 ( + 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 17 and maximum average degree less than 3 are list 2-distance ( +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

(23)

• Choosability of the square of planar subcubic graphs with large girth
• 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 ( +2)-coloring of planar graphs with girth at least 10
• Graph \(r\)-hued colorings -- a survey
• Colouring planar graphs with bounded monochromatic components
• \(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
• Degeneracy and colorings of squares of planar graphs without 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
• Choosability of the square of a planar graph with maximum degree four
• Coloring the square of a sparse graph G with almost (G) colors
• Acyclic edge-coloring of planar graphs: \(\Delta\) colors suffice when \(\Delta\) is large
• 2-distance coloring of planar graph
• 2-distance coloring of planar graphs without 4-cycles and 5-cycles
• 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
• The square of every subcubic planar graph of girth at least 6 is 7-choosable
• 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 4-coloring of planar subcubic graphs with girth at least 21

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)