A unified approach to distance-two colouring of graphs on surfaces

DOI10.1007/s00493-013-2573-2zbMath1324.05052arXiv0812.1345OpenAlexW2114523418MaRDI QIDQ2439826

Louis Esperet, Omid Amini, Jan van den Heuvel

Publication date: 17 March 2014

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

colouringsquare graphembedded graphlist colouringcyclic colouring

Mathematics Subject Classification ID

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

Related Items (19)

List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles ⋮ Chromatic numbers of exact distance graphs ⋮ Third case of the cyclic coloring conjecture ⋮ Degeneracy and colorings of squares of planar graphs without 4-cycles ⋮ Graph \(r\)-hued colorings -- a survey ⋮ Cyclic coloring of plane graphs with maximum face size 16 and 17 ⋮ Coloring Jordan Regions and Curves ⋮ Coloring the square of maximal Planar graphs with diameter two ⋮ Square Coloring Planar Graphs with Automatic Discharging ⋮ Improved square coloring of planar graphs ⋮ Edge-colouring graphs with local list sizes ⋮ Frugal, acyclic and star colourings of graphs ⋮ Distance-two coloring of sparse graphs ⋮ On the cyclic coloring conjecture ⋮ A survey on the cyclic coloring and its relaxations ⋮ Coloring squares of graphs with mad constraints ⋮ Coloring non-crossing strings ⋮ Third Case of the Cyclic Coloring Conjecture ⋮ Coloring a set of touching strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Largest planar graphs of diameter two and fixed maximum degree
• List-colouring the square of a \(K_4\)-minor-free graph
• Asymptotics of the chromatic index for multigraphs
• On the stochastic independence properties of hard-core distributions
• On cyclic colorings and their generalizations
• Coloring the square of a \(K_{4}\)-minor free graph
• Graph minors. XVI: Excluding a non-planar graph
• A new bound on the cyclic chromatic number
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A bound on the chromatic number of the square of a planar graph
• Homomorphiesätze für Graphen
• A new upper bound on the cyclic chromatic number
• List Colouring Squares of Planar Graphs
• Coloring Powers of Planar Graphs
• Coloring the square of a planar graph
• Maximum matching and a polyhedron with 0,1-vertices
• A Theorem on Coloring the Lines of a Network
• Graph colouring and the probabilistic method
• Choosability conjectures and multicircuits

This page was built for publication: A unified approach to distance-two colouring of graphs on surfaces