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

At least 5 years old · documented by

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.

References

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.