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

DOI10.1016/J.DISC.2010.03.021MaRDI QIDQ709301zbMATH OpenOpenAlexFDO

Authors Oleg V. Borodin, A. N. Glebov, André Raspaud

Publication date 18 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

3-coloringgraphplanar graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• On 3-colorable plane graphs without 5- and 7-cycles
• Planar graphs without adjacent cycles of length at most seven are 3-colorable
• Planar graphs without cycles of length from 4 to 7 are 3-colorable

Cites work

• 25 pretty graph colouring problems
• A 3-color theorem on plane graphs without 5-circuits
• A note on the three color problem
• A sufficient condition for planar graphs to be 3-colorable
• Coloring graphs with fixed genus and girth
• Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• scientific article; zbMATH DE number 54790 (Why is no real title available?)
• scientific article; zbMATH DE number 3632510 (Why is no real title available?)
• scientific article; zbMATH DE number 1109403 (Why is no real title available?)
• scientific article; zbMATH DE number 1882351 (Why is no real title available?)
• scientific article; zbMATH DE number 1882353 (Why is no real title available?)
• scientific article; zbMATH DE number 2097035 (Why is no real title available?)
• scientific article; zbMATH DE number 2097483 (Why is no real title available?)
• On 3-colorable plane graphs without 5- and 7-cycles
• On a conjecture of B. Grünbaum
• 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 cycles of length from 4 to 7 are 3-colorable
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• The color space of a graph

Cited in

(27)

• 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 cycles of length from 4 to 7 are 3-colorable
• A step towards the strong version of Havel's three color conjecture
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-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
• A refinement of choosability of graphs
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Short proofs of coloring theorems on planar graphs
• Planar graphs with cycles of length neither 4 nor 6 are \((2,0,0)\)-colorable
• Steinberg's conjecture is false
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• Distance constraints on short cycles for 3-colorability of planar graphs
• \((1,0,0)\)-colorability of planar graphs without prescribed short cycles
• The 3-colorability of planar graphs without cycles of length 4, 6 and 9
• A sufficient condition for a planar graph to be 3-colorable
• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
• Description of edges incident to 3-faces in 3-polytopes without adjacent 3-faces
• On a 3-coloring of plane graphs without monochromatic facial 3-paths
• The 3-coloring of planar graphs with adjacent triangles
• Planar graphs that exclude \(\{4, 5, 7, 8\}\)-cycles and intersecting triangles are DP-3-colorable
• Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
• Planar graphs without short even cycles are near-bipartite
• On 3-colorability of planar graphs without adjacent short cycles

This page was built for publication: Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q709301)