Third case of the cyclic coloring conjecture

DOI10.1016/J.ENDM.2015.06.003zbMATH Open1346.05070DBLPjournals/endm/HebdigeK15arXiv1501.06624OpenAlexW1564998533WikidataQ57601341 ScholiaQ57601341MaRDI QIDQ322178FDOQ322178

Michael Hebdige, Daniel Král'

Publication date: 14 October 2016

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.

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

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

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)

Cites Work

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

Cited In (6)

• Cyclic degree and cyclic coloring of 3-polytopes
• Cyclic colorings of 3-polytopes with large maximum face size
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new bound on the cyclic chromatic number
• 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)