Choosability of the square of a planar graph with maximum degree four

MaRDI QIDQ2876030zbMATH OpenFDO

Authors Daniel W. Cranston, Rok Erman, Riste Škrekovski

Publication date 15 August 2014

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.5156, http://ajc.maths.uq.edu.au/pdf/59/ajc_v59_p086.pdf

zbMATH Keywords

list chromatic numbermaximum average degree

Mathematics Subject Classification ID

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

Abstract: We study squares of planar graphs with the aim to determine their list chromatic number. We present new upper bounds for the square of a planar graph with maximum degree $Deltaleq4$. In particular $G^2$ is 5-, 6-, 7-, 8-, 12-, 14-choosable if the girth of $G$ is at least 16, 11, 9, 7, 5, 3 respectively. In fact we prove more general results, in terms of maximum average degree, that imply the results above.

Recommendations

• Choosability of the square of planar subcubic graphs with large girth
• Planar graphs of girth at least five are square ( + 2)-choosable
• List coloring the square of sparse graphs with large degree
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• New upper bound on the chromatic number of the square of a planar graph

Cited in

(20)

• Choosability of the square of planar subcubic graphs with large girth
• 2-distance list ( +2)-coloring of planar graphs with girth at least 10
• Graph \(r\)-hued colorings -- a survey
• \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\)
• Degeneracy and colorings of squares of planar graphs without 4-cycles
• Coloring squares of planar graphs with maximum degree at most five
• Coloring Powers of Planar Graphs
• Graphs of degree 4 are 5-edge-choosable
• scientific article; zbMATH DE number 1882350 (Why is no real title available?)
• An introduction to the discharging method via graph coloring
• Improper choosability of graphs and maximum average degree
• Square Coloring Planar Graphs with Automatic Discharging
• The square of every subcubic planar graph of girth at least 6 is 7-choosable
• Relaxation of Wegner's planar graph conjecture for maximum degree 4
• 2-distance \((\Delta + 1)\)-coloring of sparse graphs using the potential method
• 2-distance 4-coloring of planar subcubic graphs with girth at least 21
• List coloring the square of sparse graphs with large degree
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• List 2-distance coloring of planar graphs
• List-colouring the square of a \(K_4\)-minor-free graph

This page was built for publication: Choosability of the square of a planar graph with maximum degree four

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