Irregular spanning subgraph with minimum degree bound

Status partial high confidence

Conjecture 1.2 from arXiv:2108.02685 remains open in full generality. Fox, Luo, and Pham (2022) proved the asymptotic version for d-regular graphs when d = o(n/(log n)^{12}) via probabilistic methods. Ma and Xie (2024) obtained the first n-independent bound for d-regular graphs (within 2d^2 of the conjectured value) and proved the conjecture in strong form for d=3 regular graphs using deterministic local-adjustment techniques. Luzar, Przybylo, and Sotak (2024) independently resolved the cubic case exactly, showing deviation from n/4 is at most 1/2 (up to three exceptions). The exact bound for general graphs with minimum degree delta is still open.

Cited literature (3)

• partial On random irregular subgraphs (2022)
  Jacob Fox, Sammy Luo, Huy Tuan Pham · Random Structures & Algorithms · arXiv:2207.13651

  Proves the asymptotic version of the conjecture for d-regular graphs when d = o(n/(log n)^{12}): with high probability the irregular random subgraph satisfies m(H,k) = (1+o(1))n/(d+1) for all 0 <= k <= d.

• partial Finding irregular subgraphs via local adjustments (2024)
  Jie Ma, Shengjie Xie · arXiv preprint · arXiv:2406.05675

  Gives the first n-independent bound for d-regular graphs (vertex degree counts within 2d^2 of n/(d+1)) and proves the conjecture in strong form for cubic (d=3) regular graphs via deterministic local-adjustment methods.

• partial Degree-balanced decompositions of cubic graphs (2024)
  Borut Luzar, Jakub Przybylo, Roman Sotak · arXiv preprint · arXiv:2408.16121

  Resolves the Alon-Wei conjecture for cubic graphs, showing that every cubic graph on n vertices has a spanning subgraph where the number of vertices of each degree deviates from n/4 by at most 1/2, up to three exceptions.

Reviewer notes. The conjecture is closely related to Conjecture 1.1 (the regular-graph version). Most follow-up work addresses the regular case; the minimum-degree generalisation of Conjecture 1.2 has seen partial progress only through the special case d=3 and asymptotic results. No paper found that resolves the full conjecture for arbitrary minimum degree delta.

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