Cyclic coloring conjecture for subdivisions of simple 3-connected plane graphs

Let GG be a subdivision of a simple 33-connected plane graph. Define t(G)t(G) to be the maximum number of subdivision vertices on an edge of the underlying graph, and let Δ(G)\Delta^*(G) be the maximum face degree. Write χc(G)\chi_c(G) 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 GG satisfies

χc(G)Δ(G)+t(G)+2.\chi_c(G) \leq \Delta^*(G)+t(G)+2.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.