Planar graphs without adjacent cycles of length at most seven are 3-colorable
From MaRDI portal
Publication:1045158
DOI10.1016/j.disc.2009.08.010zbMath1221.05071MaRDI QIDQ1045158
Mickaël Montassier, Oleg V. Borodin, Andre Raspaud
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
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, 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
- 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
- On a conjecture of B. Grünbaum