Distance constraints on short cycles for 3-colorability of planar graphs

DOI10.1007/S00373-014-1476-3zbMATH Open1321.05070OpenAlexW2069158404MaRDI QIDQ497344FDOQ497344

Authors: Yingli Kang, Yingqian Wang 

Publication date: 24 September 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-014-1476-3

Recommendations

• On 3-colorability of planar graphs without adjacent short cycles
• Planar graphs without adjacent cycles of length at most seven are 3-colorable
• On 3-colorable planar graphs without short cycles
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• A sufficient condition for planar graphs to be 3-colorable

zbMATH Keywords

distancecyclesplanar graphscoloringadjacency

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Signed graphs
• Colorings of plane graphs: a survey
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• Title not available (Why is that?)
• On a conjecture of B. Grünbaum
• On 3-colorability of planar graphs without adjacent short cycles
• 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
• Title not available (Why is that?)
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• A step towards the strong version of Havel's three color conjecture
• A 3-color theorem on plane graphs without 5-circuits
• Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
• Planar graphs without adjacent cycles of length at most seven are 3-colorable
• Title not available (Why is that?)
• A relaxation of Havel's 3-color problem

Cited In (4)

• Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable
• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
• Distance constrained labelings of planar graphs with no short cycles
• \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\)

This page was built for publication: Distance constraints on short cycles for 3-colorability of planar graphs

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