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

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

Winfried Hochstättler, Felix Schröder and Raphael Steiner, “On the Complexity of Digraph Colourings and Vertex Arboricity”, arXiv:1812.02420 (2020).

Solutions 0

No solutions have been posted yet.