arxiv: 2604.19727 · v1 · submitted 2026-04-21 · 🧮 math.CO

Recognition: unknown

On Scott's odd induced subgraph conjecture and a related problem

Bo Ning

Authors on Pith no claims yet

Pith reviewed 2026-05-10 02:09 UTC · model grok-4.3

classification 🧮 math.CO

keywords odd induced subgraphScott's conjectureclaw-free graphsK1,r-free graphsline graphsC5-free graphsregular graphschromatic number

0 comments

The pith

Scott's conjecture holds for claw-free graphs without isolated vertices but fails for K_{1,r}-free graphs when r >= 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Scott conjectured that every graph without isolated vertices has an induced subgraph with all vertices of odd degree whose size is at least the chromatic number of the graph. The paper proves this conjecture for all claw-free graphs, strengthening the earlier confirmation for line graphs alone. It then exhibits families of K_{1,r}-free graphs of arbitrary size that violate the bound for every r at least 4. For the related question on the maximum odd induced subgraph in the line graph of a connected regular graph, the paper identifies C5 as the smallest counterexample while establishing the bound for all connected regular graphs that contain no C5.

Core claim

We confirm Scott's conjecture for claw-free graphs without isolated vertices, thereby strengthening the result of Wang and Wu. We also construct K_{1,r}-free graphs of arbitrarily large order to show that the conjecture fails for this broader class, for every integer r >= 4. We show that C5 is the smallest counterexample to this problem. On the positive side, we prove that if G is a connected k-regular C5-free graph on n vertices with k >= 2, then f_o(L(G)) >= n/2.

What carries the argument

The function f_o(G) measuring the size of the largest induced subgraph in which every vertex has odd degree, together with forbidden-subgraph conditions (claws or C5) that control its lower bound relative to chromatic number or total order.

If this is right

Every claw-free graph without isolated vertices satisfies f_o(G) >= |V(G)| / chi(G).
For every integer r >= 4 there exist K_{1,r}-free graphs of arbitrarily large order that violate f_o(G) >= |V(G)| / chi(G).
The line graph of C5 is the smallest connected regular graph whose line graph has f_o(L(G)) < n/2.
Every connected k-regular C5-free graph G with k >= 2 satisfies f_o(L(G)) >= n/2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The absence of claws supplies enough local control on degrees and neighborhoods to remove the factor of 2 from Scott's original bound.
Forbidding only a single star K_{1,r} is too weak a condition to guarantee the conjectured size of an odd induced subgraph.
The C5-free condition on a regular graph is sufficient to guarantee that its line graph contains an odd induced subgraph of at least half the vertices.
The exact class of regular graphs for which the line-graph bound holds may be characterized by additional forbidden cycles or girth conditions.

Load-bearing premise

The structural restrictions of being claw-free or C5-free suffice for the combinatorial counting arguments to produce a large all-odd induced subgraph without further global conditions.

What would settle it

A single claw-free graph without isolated vertices whose largest all-odd-degree induced subgraph has order strictly less than n divided by its chromatic number.

read the original abstract

For a graph $G$, let $f_o(G)$ denote the maximum order of an induced subgraph of $G$ all of whose vertices have odd degree, and let $\chi(G)$ denote the chromatic number of $G$. Scott (CPC, 1992) proved that $f_o(G) \ge |V(G)|/(2\chi(G))$ for every graph without isolated vertices, and conjectured that the factor $2$ can be removed. Wang and Wu (JGT, 2024) showed that this conjecture fails for bipartite graphs, but holds for line graphs. In this article, we confirm Scott's conjecture for claw-free graphs without isolated vertices, thereby strengthening the result of Wang and Wu. We also construct $K_{1,r}$-free graphs of arbitrarily large order to show that the conjecture fails for this broader class, for every integer $r \ge 4$. Wang and Wu also asked whether $f_o(L(G)) \ge n/2$ holds for every connected regular graph $G$ of order $n \ge 3$. We show that $C_5$ is the smallest counterexample to this problem. On the positive side, we prove that if $G$ is a connected $k$-regular $C_5$-free graph on $n$ vertices with $k \ge 2$, then $f_o(L(G)) \ge n/2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper confirms Scott's conjecture for claw-free graphs, gives explicit K_{1,r}-free counterexamples for r>=4, and pins down C5 for the line-graph question.

read the letter

The main points are the confirmation of Scott's conjecture for claw-free graphs without isolated vertices and the construction of infinite families of K_{1,r}-free counterexamples for every r at least 4. It also shows C5 is the smallest counterexample to the line-graph bound and proves that connected k-regular C5-free graphs satisfy f_o(L(G)) at least n/2. These are the concrete advances beyond the Wang-Wu results on bipartite graphs and line graphs. The claw-free case strengthens the earlier line-graph theorem, and the counterexamples are explicit enough to check by hand for small instances and scale directly. The positive C5-free result is a clean structural statement. The arguments use direct case analysis on the forbidden subgraphs and explicit constructions rather than reductions or external theorems. This keeps the work self-contained and the claims verifiable. The case analysis is the natural tool for these classes and does not appear to rest on unstated assumptions about degrees or connectivity. One limited aspect is that the positive results are tied to the specific forbidden subgraphs, so they map the boundary without resolving the general conjecture. That is standard for this style of work and not a flaw in the paper itself. This is for graph theorists working on induced subgraphs, degree conditions, or Scott-type conjectures. Readers following structural results on claw-free or line graphs will find the boundary results useful. The paper has enough specific claims and direct evidence to deserve a serious referee. I recommend sending it to peer review.

Referee Report

0 major / 2 minor

Summary. The paper confirms Scott's conjecture f_o(G) ≥ |V(G)|/χ(G) for claw-free graphs without isolated vertices (strengthening the line-graph result of Wang and Wu). It gives explicit constructions of K_{1,r}-free graphs of arbitrarily large order that violate the conjecture for every r ≥ 4. For the related question on line graphs, it shows that C_5 is the smallest counterexample to f_o(L(G)) ≥ n/2 for connected regular graphs G of order n ≥ 3, and proves that the bound holds for every connected k-regular C_5-free graph with k ≥ 2.

Significance. If the proofs and constructions are correct, the work sharpens the boundary of Scott's conjecture by establishing it for the natural superclass of claw-free graphs and by supplying infinite families of counterexamples in the K_{1,r}-free setting. The identification of C_5 as the minimal counterexample together with the positive theorem for C_5-free regular graphs supplies concrete structural information about odd-degree induced subgraphs in line graphs. The direct combinatorial arguments and explicit constructions are verifiable strengths.

minor comments (2)

In the introduction, a one-sentence reminder of the precise statement of Scott's original conjecture (including the isolated-vertex hypothesis) would help readers who have not consulted the 1992 reference.
Section 3 (the C_5-free regular case) uses several case distinctions on neighborhoods; a short table summarizing the cases and the resulting lower bounds on f_o would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, accurate summary of our contributions, and recommendation to accept the manuscript. We are pleased that the referee views the confirmation for claw-free graphs, the counterexamples for K_{1,r}-free graphs, and the resolution of the line-graph question as significant.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes its main results through direct combinatorial case analysis on forbidden subgraphs (claws, C5) and explicit constructions of K_{1,r}-free counterexamples. These arguments rely on the structural properties of the graph classes themselves and do not reduce any claimed prediction or bound to a fitted parameter, self-definition, or load-bearing self-citation. The strengthening of Wang-Wu and the C5-free line-graph bound are obtained by independent casework that remains falsifiable outside the paper's own fitted values or prior results by the same author.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper uses only standard graph-theoretic definitions and combinatorial arguments with no fitted parameters or newly invented entities.

axioms (1)

standard math Standard definitions and properties of graphs, induced subgraphs, vertex degrees, chromatic number, claw-free graphs, line graphs, and regular graphs.
These are foundational assumptions in the field of graph theory invoked throughout the proofs and constructions.

pith-pipeline@v0.9.0 · 5548 in / 1421 out tokens · 39045 ms · 2026-05-10T02:09:35.928840+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 1 canonical work pages

[1]

J. Ai, Q. Guo, G. Gutin, Y. Hao, and A. Yeo, Odd induced subgraphs in graphs of maximum degree four, preprint, arXiv:2511.15489

work page arXiv
[2]

L. W. Beineke, Characterizations of derived graphs,Journal of Combinatorial Theory9 (1970), 129–135

1970
[3]

D. M. Berman, H. Wang, and L. Wargo, Odd induced subgraphs in graphs of maximum degree three,Australasian Journal of Combinatorics15(1997), 81–85

1997
[4]

Caro, On induced subgraphs with odd degrees,Discrete Mathematics132(1994), 23–28

Y. Caro, On induced subgraphs with odd degrees,Discrete Mathematics132(1994), 23–28

1994
[5]

Y. Caro, I. Krasikov, and Y. Roditty, On induced subgraphs of trees, with restricted degrees, Discrete Mathematics125(1994), 101–106

1994
[6]

Ferber and M

A. Ferber and M. Krivelevich, Every graph contains a linearly sized induced subgraph with all degrees odd,Advances in Mathematics406(2022), Paper No. 108534. 7

2022
[7]

Grötzsch, Zur Theorie der diskreten Gebilde

H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. (German) Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 (1958/59), 109–120

1958
[8]

X. Hou, L. Yu, J. Li, and B. Liu, Odd induced subgraphs in graphs with treewidth at most two,Graphs and Combinatorics34(2018), 535–544

2018
[9]

Kano, Factors of regular graphs,Journal of Combinatorial Theory, Series B41(1986), 27–36

M. Kano, Factors of regular graphs,Journal of Combinatorial Theory, Series B41(1986), 27–36

1986
[10]

Lovász,Combinatorial Problems and Exercises, 2nd ed., AMS Chelsea Publishing, Providence, RI, 1993

L. Lovász,Combinatorial Problems and Exercises, 2nd ed., AMS Chelsea Publishing, Providence, RI, 1993

1993
[11]

H. M. Mulder, Julius Petersen’s theory of regular graphs,Discrete Mathematics100 (1992), 157–175

1992
[12]

Petersen, Die Theorie der regulären graphs,Acta Mathematica15 (1891), 193–220

J. Petersen, Die Theorie der regulären graphs,Acta Mathematica15 (1891), 193–220
[13]

A. J. Radcliffe and A. D. Scott, Every tree contains a large induced subgraph with all degrees odd,Discrete Mathematics140(1995), 275–279

1995
[14]

M. Rao, J. Hou, and Q. Zeng, Odd induced subgraphs in planar graphs with large girth,Graphs and Combinatorics38(2022), Paper No. 105

2022
[15]

A. D. Scott, Large induced subgraphs with all degrees odd,Combinatorics, Probability and Computing1(1992), 335–349

1992
[16]

A. D. Scott, On induced subgraphs with all degrees odd,Graphs Combin.17(2001), 539–553

2001
[17]

Wang and B

T. Wang and B. Wu, Maximum odd induced subgraph of a graph concerning its chromatic number,Journal of Graph Theory107(2024), 578–596. 8

2024