The circular homomorphism conjecture for planar graphs of girth at least 4k4k

At least 7 years old · documented by

Let kk be a positive integer and let GG be a planar graph whose girth is at least 4k4k. A homomorphism from GG to C2k+1C_{2k+1} is a map preserving adjacency.

Circular homomorphism conjecture. Every planar graph GG of girth at least 4k4k admits a homomorphism to C2k+1C_{2k+1}. Equivalently,

χc(G)≤2k+1k.\chi_c(G) \leq \frac{2k+1}{k}.

This is a well-known conjecture giving a homomorphism bound for planar graphs of large girth; its resolution status is not specified in the source.

References

Primary source

Winfried Hochstättler, Felix Schröder and Raphael Steiner, “On the Complexity of Digraph Colourings and Vertex Arboricity”, arXiv:1812.02420 (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.