Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable

DOI10.1016/J.DISC.2016.06.011MaRDI QIDQ738860zbMATH OpenOpenAlexFDO

Authors Chuanni Zhang, Min Chen, Yingqian Wang

Publication date 16 August 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphdischargingreducible configuration\((d_1,d_2,\ldots,d_k)\)-coloring

Mathematics Subject Classification ID

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

Recommendations

• Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
• Planar graphs without cycles of length 4 or 7 are \((2, 0, 0)\)-colorable
• Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
• Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-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 1109403 (Why is no real title available?)
• scientific article; zbMATH DE number 2097035 (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 relaxation of Steinberg's conjecture
• A relaxation of the Bordeaux conjecture
• A relaxation of the strong Bordeaux Conjecture
• A sufficient condition for planar graphs to be 3-colorable
• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• Distance constraints on short cycles for 3-colorability of planar graphs
• Graph theory
• Improper colorability of planar graphs without prescribed short cycles
• On 3-colorability of planar graphs without adjacent short cycles
• On \((3,1)^*\)-coloring of plane graphs
• 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 4 or 5 are (3,0,0)-colorable
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-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
• Some simplified NP-complete graph problems
• Steinberg's conjecture is false
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• \((1,0,0)\)-colorability of planar graphs without prescribed short cycles

Cited in

(4)

• Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable
• Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
• A relaxation of Novosibirsk 3-color conjecture
• Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable

This page was built for publication: Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable

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