Circular-colouring density conjecture for 4-critical graphs

Let pp and qq be integers satisfying 3<pq<43<\frac{p}{q}<4. A (p,q)(p,q)-colouring is a graph homomorphism to the circular clique with vertex set {0,1,,p1}\{0,1,\ldots,p-1\}, in which two vertices i,ji,j are adjacent when qijpqq\leq|i-j|\leq p-q. Let GG be a 44-critical graph, meaning that χ(G)=4\chi(G)=4 while every proper subgraph has chromatic number 33.

Circular-colouring density conjecture. If GG has no (p,q)(p,q)-colouring, then there exist positive rational numbers εp,q\varepsilon_{p,q} and cp,qc_{p,q}, depending on pp and qq, such that

e(G)(5+εp,q)cp,q3.e(G)\geq\frac{(5+\varepsilon_{p,q})-c_{p,q}}{3}.

The source describes this as a strong conjecture motivated by structural results on 44-critical graphs without such colourings. The displayed bound appears exactly as stated in the source, and no resolution is given.

Sources & referencesView supporting material

Primary source

Benjamin Moore, “Sparse 4-critical graphs have low circular chromatic number”, arXiv:2007.15556 (2020).

Additional references

2 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1812.02420.

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.