Erdős–Hajnal–Thomassen conjecture on high-chromatic subgraphs of prescribed girth and average degree

Let kk be a positive integer and let g3g\ge3 be an integer. For a graph, its chromatic number is denoted by χ(G)\chi(G), its average degree is the average of its vertex degrees, and its girth is the length of its shortest cycle. Erdős–Hajnal–Thomassen conjecture. For every positive integers kk and g3g\ge3, there exists a positive number c(k,g)c(k,g) such that every graph with chromatic number at least c(k,g)c(k,g) contains a subgraph of girth at least gg and with average degree at least kk. The source presents this as a weakening of the Erdős–Hajnal and Thomassen conjectures and gives no resolution; it 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.