Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable

zbMath1119.05037MaRDI QIDQ2371269

Tommy R. Jensen, Oleg V. Borodin, Alekseĭ Nikolaevich Glebov, Andre Raspaud

Publication date: 2 July 2007

Published in: Sibirskie Èlektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/53348

zbMATH Keywords

Euler's formula; color-4-critical graph; plane graph without triangles

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

Steinberg's conjecture is false, Distance constraints on short cycles for 3-colorability of planar graphs, 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, Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, Planar graphs without adjacent cycles of length at most seven are 3-colorable, Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-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, A relaxation of Novosibirsk 3-color conjecture, Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable, Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph, Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable