Erdős–Hajnal–Thomassen conjecture on high-chromatic subgraphs of prescribed girth and average degree
Erdős–Hajnal–Thomassen conjecture on high-chromatic subgraphs of prescribed girth and average degree
Let be a positive integer and let be an integer. For a graph, its chromatic number is denoted by , 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 and , there exists a positive number such that every graph with chromatic number at least contains a subgraph of girth at least and with average degree at least . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.