Dvořák–Postle edge conjecture for C5C_5-critical graphs

About 6 years old · traced to

For a graph HH, an HH-critical graph is a graph that admits no homomorphism to HH, while every proper subgraph does. Here C5C_5 denotes the cycle on five vertices, and e(G)=∣E(G)∣e(G)=|E(G)|, v(G)=∣V(G)∣v(G)=|V(G)|.

Dvořák–Postle conjecture. If GG is C5C_5-critical, then

e(G)≥14v(G)−911.e(G)\geq\frac{14v(G)-9}{11}.

This conjecture concerns the density of graphs critical for homomorphisms to the five-cycle and is stated after a weaker proven bound in the source; no resolution is supplied here.

References

Primary source

Benjamin Moore, “Sparse 4-critical graphs have low circular chromatic number”, arXiv:2007.15556 (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.