A relaxation of Havel's 3-color problem

DOI10.1016/J.IPL.2008.02.003zbMath1185.05062OpenAlexW2062686295MaRDI QIDQ963412

Mickaël Montassier, Ying Qian Wang, Wei Fan Wang, Andre Raspaud

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.02.003

zbMATH Keywords

combinatorial problemsgraph algorithms3-choosabilitycycle distance

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)

Related Items (4)

A note on 3-choosability of plane graphs under distance restrictions ⋮ Distance constraints on short cycles for 3-colorability of planar graphs ⋮ Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable ⋮ Planar graphs without adjacent cycles of length at most seven are 3-colorable

Cites Work

• Some counterexamples associated with the three-color problem
• 3-list-coloring planar graphs of girth 5
• A not 3-choosable planar graph without 3-cycles
• Bordeaux 3-color conjecture and 3-choosability
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

This page was built for publication: A relaxation of Havel's 3-color problem