Degree-weighted independence vs Hall ratio gap

Problem 5 · arXiv:1812.07327

arXiv Problem high confidence— first stated 2020-01-30

Authors: Zdeněk Dvořák, Patrice Ossona de Mendez, Hehui Wu

Status solved high confidence

Problem 5 was affirmatively solved by Raphael Steiner (arXiv:2411.16465, published in Combinatorica 2025). Theorem 1.5 of that paper constructs, for every fixed δ > 0 and sufficiently large n, an n-vertex graph G with χ_f(G) ≥ log log n / (50 log log log n), ρ(G) ≤ 4 + δ, and α_{deg_H}(H) ≥ |E(H)| / (4 + δ) for every subgraph H ⊆ G, directly answering the problem in the affirmative. The companion arXiv:2007.11853 (Dvořák, on weighted sublinear separators) does not bear on Problem 5.

Cited literature (1)

proof Fractional chromatic number vs. Hall ratio (2024)

Raphael Steiner · Combinatorica · arXiv:2411.16465 · doi:10.1007/s00493-025-00164-0

Theorem 1.5 constructs graphs with ρ(G) ≤ 4+δ, arbitrarily large fractional chromatic number, and α_{deg_H}(H) ≥ |E(H)|/(4+δ) for every H ⊆ G, affirmatively solving Problem 5 (labeled Problem 1.4 in this paper).

Reviewer notes. Problem 5 is fully resolved. The two duplicate entries for arXiv:2007.11853 in the internal references (fuzz scores 71 and 67) are false positives; that paper concerns weighted balanced separators and shares only authorship (Dvořák) with the source paper.

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

Problem. Do there exist, for some constant $c > 0$, graphs $G$ of arbitrarily large fractional chromatic number such that $\rho(G) \leq c$ and $\alpha_{\deg_H}(H) \geq |E(H)|/c$ for every $H \subseteq G$?

Context

To lower-bound $\chi_f$ of the probabilistically constructed graphs in Theorem 1, the authors assign vertex weights proportional to degrees. Problem 5 asks whether such degree-weighted independence certificates can simultaneously be large while the ordinary Hall ratio remains bounded, motivating a search for intermediate weight families $\mathcal{F}$ between $\{0,1\}$-valued weights (Hall ratio) and all non-negative weights (fractional chromatic number).

Notes. PDF source — the notation $\alpha_{\deg_H}$ for the degree-weighted maximum independent set weight may be slightly garbled.

Source paper

1-subdivisions, fractional chromatic number and Hall ratio
Zdeněk Dvořák, Patrice Ossona de Mendez, Hehui Wu · 2020-01-30
https://arxiv.org/abs/1812.07327 PDF source