Planar graphs without adjacent cycles of length at most seven are 3-colorable

DOI10.1016/j.disc.2009.08.010zbMath1221.05071OpenAlexW2071241856MaRDI QIDQ1045158

Andre Raspaud, Oleg V. Borodin, Mickaël Montassier

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2009.08.010

zbMATH Keywords

the 3-color problem

Mathematics Subject Classification ID

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

Related Items (max. 100)

Facially-constrained colorings of plane graphs: a survey ⋮ A step towards the strong version of Havel's three color conjecture ⋮ Short proofs of coloring theorems on planar graphs ⋮ Distance constraints on short cycles for 3-colorability of planar graphs ⋮ A toughness condition for a spanning tree with bounded total excesses ⋮ Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable ⋮ Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable ⋮ Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable ⋮ Every planar graph without adjacent cycles of length at most 8 is 3-choosable ⋮ Note on 3-choosability of planar graphs with maximum degree 4

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A relaxation of Havel's 3-color problem
• Some counterexamples associated with the three-color problem
• Some simplified NP-complete graph problems
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• A sufficient condition for planar graphs to be 3-colorable
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• A note on the three color problem
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• A 3-color theorem on plane graphs without 5-circuits
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• On a conjecture of B. Grünbaum

This page was built for publication: Planar graphs without adjacent cycles of length at most seven are 3-colorable