Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles

zbMATH Open1274.05113MaRDI QIDQ2857451FDOQ2857451

Authors: Peter Whalen 

Publication date: 1 November 2013

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S1571065311002034

Recommendations

• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Three-colourability of planar graphs with no 5- or triangular \(\{3,6\}\)-cycles
• Plane graphs without cycles of length 4, 6, 7 or 8 are 3-colorable
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• A note on the three color problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Some simplified NP-complete graph problems
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• 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
• Title not available (Why is that?)
• A 3-color theorem on plane graphs without 5-circuits
• Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable

Cited In (10)

• Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three coloring via triangle counting
• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
• A note on the three color problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles
• New restrictions on defective coloring with applications to Steinberg-type graphs
• Triangle-free planar graphs with at most \(64^{n^{0.731}}\) 3-colorings
• Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
• Plane graphs without cycles of length 4, 6, 7 or 8 are 3-colorable

This page was built for publication: Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles

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