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

DOI10.1016/j.disc.2009.08.010zbMath1221.05071MaRDI 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

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

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 \((1,1,0)\)-colorable, A step towards the strong version of Havel's three color conjecture, Planar graphs without adjacent cycles of length at most five are (2, 0, 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, Facially-constrained colorings of plane graphs: a survey, Short proofs of coloring theorems on planar graphs

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