Graph-theory open problems

Fractional Hadwiger

Medium ★★ Graph Theory accessible to undergrads
Authors: Harvey, Daniel J., Reed, Bruce A., Seymour, Paul D., Wood, David R.— posted by David Wood on 2014-03-16

Status open medium confidence

No verified post-2014 paper resolves any of the three conjectures (a) $\chi_f(G)\leq\mathrm{had}(G)$, (b) $\chi(G)\leq\mathrm{had}_f(G)$, or (c) $\chi_f(G)\leq\mathrm{had}_f(G)$. The best published upper bound on $\chi_f$ in terms of $\mathrm{had}$ remains Reed and Seymour's 1998 result $\chi_f(G)\leq 2\,\mathrm{had}(G)$; recent improvements toward Hadwiger's conjecture by Norin, Postle and Song concern $\chi(G)$ versus $\mathrm{had}(G)$ rather than the fractional variants.

Reviewer notes. Searches surfaced recent work on the (integer) Hadwiger conjecture (Norin-Postle-Song, Steiner 2023 on topological bounds, Postle's improved bounds) and on related variants (odd Hadwiger, balanced chromatic number, strong chromatic index), but none of the verified items prove or disprove any of conjectures (a), (b), (c). The Fox 2011 paper (arXiv:1108.4953) introducing $\mathrm{had}_f$ predates the OPG posting date of 2014-03-16, so it cannot count as 'since posted'. I did not exhaustively search for unpublished theses or short notes, so a small probability remains that incremental progress exists in less indexed venues; status reported as 'open' rather than 'unclear' because the OPG-listed Reed-Seymour bound $\chi_f\leq 2\,\mathrm{had}$ from 1998 is still the state of the art quoted in surveys.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Conjecture. For every graph $ G $ , (a) $ \chi_f(G)\leq\text{had}(G) $ (b) $ \chi(G)\leq\text{had}_f(G) $ (c) $ \chi_f(G)\leq\text{had}_f(G) $ .
Keywords: fractional coloring, minors

Discussion

Here $ \chi $ is the chromatic number, $ \chi_f $ is the fractional chromatic number, $ \text{had} $ is the Hadwiger number, and $ \text{had}_f $ is the fractional Hadwiger number (which was recently introduced independently by Fox [F] and Pedersen [P]). It is well known and easily proved (see [HW]) that $ \chi_f(G)\leq\chi(G)\text{ and }\text{had}(G)\leq\text{had}_f(G)\leq\text{tw}(G)+1, $ where $ \text{tw}(G) $ is the treewidth of $ G $ . Hadwiger's famous conjecture, $ \chi(G)\leq\text{had}(G) $ , bridges the gap in the above inequalities. The above conjectures therefore are weaker than Hadwiger's conjecture. Note that Conjecture (a) implies Conjecture (c), and Conjecture (b) implies Conjecture (c). Note that Reed and Seymour [RS] proved that $ \chi_f(G)\leq2\,\text{had}(G) $ . Conjecture (a) is due to Reed and Seymour [RS]. Conjecture (b) is due to Harvey and Wood [HW]. Conjecture (c) is independently due to Harvey and Wood [HW] and Pedersen [P]. Pedersen [P] presents a natural equivalent formulation of Conjecture (c).

Bibliography