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

DOI10.1007/S00373-014-1476-3MaRDI QIDQ497344zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• 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 2097035 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• A 3-color theorem on plane graphs without 5-circuits
• A note on the three color problem
• A relaxation of Havel's 3-color problem
• A step towards the strong version of Havel's three color conjecture
• A sufficient condition for planar graphs to be 3-colorable
• Colorings of plane graphs: a survey
• Graph theory
• On 3-colorability of planar graphs without adjacent short cycles
• On a conjecture of B. Grünbaum
• 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
• 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
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• Signed graphs
• Some simplified NP-complete graph problems
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

Cited in

(4)

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

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)