Fractional Erdős–Hajnal conjecture for subgraphs of prescribed girth

About 8 years old · traced to

Let x≥1x\ge1 be real and let g≥3g\ge3 be an integer. For a graph GG, let χf(G)\chi_f(G) denote its fractional chromatic number, and let the girth of a graph be the length of its shortest cycle. Fractional Erdős–Hajnal conjecture. For every real number x≥1x\ge1 and any integer g≥3g\ge3, there exists a positive number k(x,g)k(x,g) such that every graph GG with χf(G)≥k(x,g)\chi_f(G)\ge k(x,g) contains a subgraph HH of girth at least gg and with χf(H)≥x\chi_f(H)\ge x. This extends the paper’s proved triangle-free case, corresponding to g=4g=4, to arbitrary prescribed girth; the proposed general statement remains open.

References

Primary source

Bojan Mohar and Hehui Wu, “Triangle-free subgraphs with large fractional chromatic number”, arXiv:1808.01605 (2018).

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.