Third case of the cyclic coloring conjecture

DOI10.1016/J.ENDM.2015.06.003MaRDI QIDQ322178zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael Hebdige, Daniel Král'

Publication date 14 October 2016

Full work available at URL https://arxiv.org/abs/1501.06624

zbMATH Keywords

graph coloringplanar graphscyclic coloringfacial coloring

Mathematics Subject Classification ID

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

Abstract: The Cyclic Coloring Conjecture asserts that the vertices of every plane graph with maximum face size D can be colored using at most 3D/2 colors in such a way that no face is incident with two vertices of the same color. The Cyclic Coloring Conjecture has been proven only for two values of D: the case D=3 is equivalent to the Four Color Theorem and the case D=4 is equivalent to Borodin's Six Color Theorem, which says that every graph that can be drawn in the plane with each edge crossed by at most one other edge is 6-colorable. We prove the case D=6 of the conjecture.

Recommendations

• Third case of the cyclic coloring conjecture
• Cyclic 9-coloring of plane graphs with maximum face degree six.
• Cyclic coloring of plane graphs with maximum face size 16 and 17
• Cyclic chromatic number of 3-connected plane graphs
• A note on cyclic chromatic number

Cites work

• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• scientific article; zbMATH DE number 1275149 (Why is no real title available?)
• scientific article; zbMATH DE number 3310750 (Why is no real title available?)
• 3-Facial Coloring of Plane Graphs
• A new bound on the cyclic chromatic number
• A new proof of the 6 color theorem
• A unified approach to distance-two colouring of graphs on surfaces
• Colorings of plane graphs: a survey
• Cyclic chromatic number of 3-connected plane graphs
• Cyclic coloration of 3-polytopes
• Cyclic coloring of plane graphs
• Cyclic, diagonal and facial colorings
• Cyclic, diagonal and facial colorings -- a missing case
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Facial colorings using Hall's theorem
• On cyclic colorings and their generalizations
• On vertex types and cyclic colourings of 3-connected plane graphs

Cited in

(9)

• Cyclic degree and cyclic coloring of 3-polytopes
• Cyclic colorings of 3-polytopes with large maximum face size
• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• Cyclic 9-coloring of plane graphs with maximum face degree six.
• Third case of the cyclic coloring conjecture
• scientific article; zbMATH DE number 5139507 (Why is no real title available?)
• A new bound on the cyclic chromatic number
• On unique coloring of planar graphs
• 3-consecutive C-colorings of graphs

This page was built for publication: Third case of the cyclic coloring conjecture

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