Scott's odd induced subgraph conjecture

Let GG be a finite simple graph, let fo(G)f_o(G) be the maximum order of an induced subgraph of GG whose every vertex has odd degree, and let χ(G)\chi(G) be the chromatic number of GG. Assume that GG has no isolated vertices. Scott's conjecture.

fo(G)V(G)χ(G).f_o(G)\geq \frac{|V(G)|}{\chi(G)}.

Scott's conjecture strengthens his proven bound by removing the factor 22. The conjecture is a central chromatic formulation of the problem of finding large odd induced subgraphs; the supplied text gives no resolution status for this claim.

Sources & referencesView supporting material

Primary source

Bo Ning, “On Scott's odd induced subgraph conjecture and a related problem”, arXiv:2604.19727 (2026).

Additional references

6 papers in this index state this conjecture (2011–2026). The statement above is taken from the most recent of them; the others are arXiv:2211.10895, arXiv:2009.02953, arXiv:1406.0338, arXiv:1308.6678, arXiv:1107.3491.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.