List Colouring Squares of Planar Graphs

DOI10.1016/J.ENDM.2007.07.079MaRDI QIDQ3503513zbMATH OpenOpenAlexFDO

Authors Frédéric Havet, Jan van den Heuvel, Colin McDiarmid, Bruce Reed

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

list colouringplanar graphsquare of a graph

Mathematics Subject Classification ID

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

Abstract: In 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $Deltage8$ is at most $$. We show that it is at most $frac32Delta(1+o(1))$ (where the $o(1)$ is as $Deltao+infty$), and indeed that this is true for the list chromatic number and for more general classes of graphs.

Recommendations

• List colourings of planar graphs
• List-colouring the square of an outerplanar graph.
• List-coloring the squares of planar graphs without 4-cycles and 5-cycles
• List-coloring the square of a subcubic graph
• Coloring the square of a planar graph
• Multiple list colouring of planar graphs
• List colourings of planar graphs. (Reprint)
• List 4-colouring of planar graphs
• List coloring triangle-free planar graphs
• List-colourings of graphs

Cites work

• A bound on the chromatic number of the square of a planar graph
• Choosability conjectures and multicircuits
• scientific article; zbMATH DE number 1523257 (Why is no real title available?)
• List Colouring Squares of Planar Graphs

Cited in

(52)

• List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six
• A Brooks-type bound for squares of \(K_{4}\)-minor-free graphs
• List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles
• On list r-hued coloring of planar graphs
• The square of a planar cubic graph is 7-colorable
• The complexity of frugal colouring
• 2-distance list \((\varDelta +3)\)-coloring of sparse graphs
• 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
• List (p,q)-coloring of sparse plane graphs
• Coloring squares of planar graphs with girth six
• A unified approach to distance-two colouring of graphs on surfaces
• A bound on the chromatic number of the square of a planar graph
• Painting squares in \(\Delta^2-1\) shades
• Degeneracy and colorings of squares of planar graphs without 4-cycles
• Exact square coloring of subcubic planar graphs
• Cyclic coloring of plane graphs with maximum face size 16 and 17
• Improved square coloring of planar graphs
• Third case of the cyclic coloring conjecture
• List 2-distance coloring of planar graphs without short cycles
• Coloring plane graphs with independent crossings
• List Colouring Squares of Planar Graphs
• List-coloring the square of a subcubic graph
• List-Coloring Squares of Sparse Subcubic Graphs
• Graphs with maximum degree 17 and maximum average degree less than 3 are list 2-distance ( +2)-colorable
• List Improper Colourings of Planar Graphs
• Distributed colorings for collision-free routing in sink-centric sensor networks
• Randomly colouring graphs (a combinatorial view)
• Coloring the square of Sierpiński graphs
• List-coloring the squares of planar graphs without 4-cycles and 5-cycles
• Angular Resolutions: Around Vertices and Crossings
• 2-distance choice number of planar graphs with maximal degree no more than 4
• An introduction to the discharging method via graph coloring
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Square Coloring Planar Graphs with Automatic Discharging
• 2-distance coloring of planar graphs without adjacent 5-cycles
• A note on 3-distance coloring of planar graphs
• Bounding clique size in squares of planar graphs
• Relaxation of Wegner's planar graph conjecture for maximum degree 4
• Cyclic colorings of plane graphs with independent faces
• Tree-like distance colouring for planar graphs of sufficient girth
• Eigenvalue bounds for the distance-t chromatic number of a graph and their application to Lee codes
• The r-dynamic chromatic number is bounded in the strong 2-coloring number
• List 2-distance coloring of planar graphs without 4- and 5-cycles
• Coloring squares of planar graphs with small maximum degree
• Coloring the square of the Cartesian product of two cycles
• The distance coloring of graphs
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• The L(p, q)-labelling of planar graphs without 4-cycles
• The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes
• Facial colorings using Hall's theorem

This page was built for publication: List Colouring Squares of Planar Graphs

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