Cyclic coloring conjecture for subdivisions of simple 3-connected plane graphs
Cyclic coloring conjecture for subdivisions of simple 3-connected plane graphs
Let be a subdivision of a simple -connected plane graph. Define to be the maximum number of subdivision vertices on an edge of the underlying graph, and let be the maximum face degree. Write for the minimum number of colors in a cyclic coloring, meaning a vertex coloring in which vertices incident with the same face receive distinct colors.
Subdivision cyclic coloring conjecture. Every such graph satisfies
The source introduces this as a new conjecture combining the Plummer–Toft conjecture with the corresponding subdivision case of the earlier conjecture. Its status is not resolved in the supplied text.
Sources & referencesView supporting material
Primary source
Stanislav Jendrol and Roman Sotak, “On the cyclic coloring conjecture”, arXiv:2009.10436 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.