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

Let x1x\ge1 be real and let g3g\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 x1x\ge1 and any integer g3g\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.

Sources & referencesView supporting material

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.