High-girth subgraphs with large χ_f

Conjecture 4 · arXiv:1808.01605

arXiv Conjecture medium confidence— first stated 2018-08-05

Authors: Bojan Mohar, Hehui Wu

Status open medium confidence

Conjecture 4 from arXiv:1808.01605 asks whether for every real x≥1 and integer g≥3 there exists k(x,g) such that every graph G with χ_f(G)≥k(x,g) contains a subgraph H of girth at least g with χ_f(H)≥x. The source paper itself establishes the g=4 case (Theorem 3), which is the fractional analog of Rödl's 1977 result on chromatic number. No subsequent paper resolving the conjecture for g≥5 was found across targeted web searches; the conjecture appears to remain open as of 2026.

Reviewer notes. The conjecture is the natural full generalization of the paper's main Theorem 3 (g=4 case) to all girth g≥3, paralleling the classical Erdős-Hajnal / Rödl program for ordinary chromatic number. None of the five supplied internal references address this conjecture. No follow-up paper proving or disproving the full statement for g≥5 was found; the conjecture is 8 years old, so medium rather than high confidence is appropriate.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every real number $x \geq 1$ and any integer $g \geq 3$, there exists a positive number $k(x,g)$ such that every graph $G$ with $\chi_f(G) \geq k(x,g)$ contains a subgraph $H$ of girth at least $g$ and with $\chi_f(H) \geq x$.

Context

Proposed immediately after Theorem 3 as the natural full generalisation to arbitrary girth. Theorem 3 of this paper establishes the case $g = 4$ (triangle-free subgraphs), and Conjecture 4 asks whether the same holds for every girth.

Notes. PDF source — math appears readable.

Source paper

Triangle-free subgraphs with large fractional chromatic number
Bojan Mohar, Hehui Wu · 2018-08-05
https://arxiv.org/abs/1808.01605 PDF source