Pith. sign in

REVIEW 3 major objections 4 minor 18 references

Induced subgraphs of graphs with large deficiency

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Graphs with large matching gap must contain an induced bone.

desk verdict Solid, useful extension of the bone-free deficiency bound, with three concrete fixable glitches in the extremal constructions and one index typo in the main proof. read the letter →

arxiv 2505.15149 v1 pith:AYKJSJAY submitted 2025-05-21 math.CO

Jin Sun , Xinmin Hou This is my paper · ORCID
classification math.CO MSC 05C7005C6905C35
keywords deficiencybonelocalindependencenumberinducedsubgraphmatchinglevellingextremalboundadmittingset
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes a matching-theoretic counterpart of the classical hole theorems for chromatic number. It considers connected graphs whose maximum matching leaves many vertices unmatched (large deficiency) and whose local independence number is small, and it shows that such graphs must contain an induced bone, the tree obtained by hanging two pendant edges from each end of a path. The main theorem bounds the deficiency by $m(n-3)(n-2)^{(m-3)/2}+1$ whenever the only bones present are odd and no two allowed lengths differ by one; for $m=3$ the bound becomes $2n-5$ and is attained. Companion results give exact bounds for two even-bone families under clique restrictions, and the paper provides an algorithm that constructs a matching realizing each upper bound.

What carries the argument

The argument rests on a levelling of the graph from a 'snail head,' a vertex with two pendant neighbors whose existence in every nontrivial deficiency-critical graph follows from the paper's Lemma 2.1. The Levelling-Matching algorithm builds a large matching level by level, leaving only the sets $Z_i$ unmatched, so bounding the deficiency reduces to bounding those levels. A private-neighbor function propagates vertices upward through the levels, and the 'friendly level' of two shortest paths measures how far they share vertices. Lemma 2.9 is the engine: it shows that two snail heads with non-adjacent children force induced bones of four specific indices, $j+1$, $p-j$, $N-j$, and $N+p-2j-1$, provided the paths meet only at the friendly level and the pendant beards touch nothing else. The closure condition on $A$ turns each forced bone into a contradiction, which collapses the possible unmatched levels.

What would settle it

Construct a connected $K_{1,n}$-free graph whose only induced bones have odd lengths from a set $A$ satisfying $p+q\pm 1\notin A$, then run the paper's Levelling-Matching algorithm from the snail head whose existence is guaranteed by Corollary 2.3: if some odd level $i$ yields $|Z_i|>(n-3)^2(n-2)^{(i-3)/2}$ for $3\le i<m$ or $|Z_i|>(n-3)(n-2)^{(m-3)/2}$ for $i\ge m$ while no forbidden bone index appears, the bound is false. Such a counterexample would show up as an unaccounted chord between the two friendly paths beyond the friendly level, changing a bone index into the admitting set instead of contradicting it.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.4: for odd $m\ge 3$ and an admitting set $A$ of odd integers in which no element can be written as $p+q+1$ or $p+q-1$ with $p,q\ge m$ in $A$, every connected graph with $\alpha_l(G)<n$ and all its bones in $\{B_i:i\in A\}$ satisfies $\mathrm{def}(G)\le m(n-3)(n-2)^{(m-3)/2}+1$, and when $m=3$ the inequality improves to $\mathrm{def}(G)\le 2n-5$. The $m=3$ bound is tight, and the general bound is asymptotically optimal in the order of $n$. This is the claimed analog, for the parameter pair (deficiency, local independence number), of the long-odd-hole theorems: bounded local independence plays the role of bounded clique number, and the presence of admissible odd bones forces the deficiency to be controlled.

Load-bearing premise

The proof depends on the assumption that when it joins two shortest paths to build an induced bone, the only connections between them are the allowed ones at the shared friendly level and possibly one direct edge; if an extra edge appeared in some extremal example, the bone's length would change and the closure condition on the admitting set might no longer give a contradiction.

Editorial extensions

If this is right

  • For $m=3$ the bound $\mathrm{def}(G)\le 2n-5$ is exact: the construction $BS^p_{n-2}$ attains it, so no improvement is possible in that case.
  • For odd $m\ge 5$ the exponent in the leading term $(n-3)(n-2)^{(m-3)/2}$ cannot be improved, and the tree $T_{m,n}$ matches it asymptotically; the exact constant is left open in the paper's Problem 1.7.
  • A nonzero unmatched level $Z_i$ can occur only when $i$ is an admissible odd bone index or $i=1$, so large deficiency is localized at levels that themselves carry a forbidden bone.
  • When two admissible odd lengths satisfy $q=2p+1$ or $q=2p-1$, the bounds jump respectively to $3n-8$ and $n^2-3n+1$, with deficiency-critical extremal graphs $T^p_{n-2}$ and $S^p_{n-1}$.
  • For even bones the deficiency is unbounded without extra hypotheses, but with clique restrictions one gets tight bounds: $(m-1)(n-3)+1$ for a single even bone, and $2n-6$ when all even bones are allowed and triangles are forbidden.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the exact constant for general odd $m$ follows the pattern of the $m=3$ and even-bone cases, the true maximum is likely a polynomial in $n$ of degree $(m-1)/2$ with leading coefficient $1$, matching Construction B rather than the theorem's coefficient $m$; testing small $m=5$ would settle this.
  • The Levelling-Matching algorithm is constructive, so the structural theorem doubles as a way to certify the bound by outputting a matching whose uncovered vertices are confined to levels of admissible bones in these graph classes.
  • The closure condition $p+q\pm 1\notin A$ mirrors exclusion conditions used in chromatic-boundedness proofs, so the same two-path gluing mechanism may extend to other closure rules, such as forbidding $2p-q$ or arithmetic progressions, and yield different extremal functions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces an analog of the Scott--Seymour induced-hole theorems for the parameter pair (deficiency, local independence number), replacing holes by induced 'bones' B_i (a path of length i with two pendant edges attached to each end). The main result, Theorem 1.4, asserts that for odd m and an odd admitting set A closed under p+q+1, p+q-1 notin A for all p,q in A with p,q >= m, every connected G in G(A) with alpha_l(G) < n satisfies def(G) <= m(n-3)(n-2)^((m-3)/2)+1, and def(G) <= 2n-5 when m=3. The proof develops a levelling/matching algorithm, introduces private-neighbor layers L'_j, and bounds |Z_i| level by level using induced-bone obstructions. Explicit constructions show the m=3 bound is tight and the general bound is asymptotically optimal. Secondary results treat admitting sets {p,2p+1} and {p,2p-1}, and even-bone-free graphs with K_m or K_3 excluded.

Significance. If the main theorem is established, it is a genuine quantitative extension of the classical near-perfect matching results of Las Vergnas, Sumner, and Fujita et al. to graphs with bounded local independence number that exclude specific induced bones. The algorithmic levelling method is constructive and the extremal constructions are explicit, so the paper would contribute a useful new template for (def, alpha_l)-boundedness. The main inequality is supported by a long, structured proof with machine-checkable local steps, but as written the proof contains a load-bearing indexing error in Claim 7 and a gap in Lemma 2.9 for equal endpoint levels; these block verification of the central claim until corrected.

major comments (3)
  1. [Section 3, Claim 7] The private-neighbor iteration count is wrong. For u in L'_{i-m+1}, the map p increases the level by exactly one, so p^{(i-j-1)}(u) lies in L'_{2i-m-j}, not in L'_{i-1}. For j < i-m this level exceeds the domain of p (defined only up to L'_{i-2}), and for j = i-m the expression lands in L'_i rather than L'_{i-1}. The subsequent application of Lemma 2.9 to P_{p^{(i-j-1)}(u)} is therefore undefined as written. Replacing i-j-1 by m-2 sends u to L'_{i-1} and preserves the friendly level j; with that correction Lemma 2.9 yields i-j and 2i-2j-1 in A, giving exactly the intended contradiction. Since Claim 7 supplies the essential bound for every |Z_i| with i >= m and is used in both final summations of Theorem 1.4, this correction is load-bearing.
  2. [Lemma 2.9, statement and proof] The conclusion N+p-2j-1 in A is obtained by forming V(xP_xx_jP_uu) union {v,w,x+,x-} as an induced bone. When p=N, the vertices v,w and x+,x- all lie in the same level L_N, and the stated hypotheses (1)-(3) do not exclude edges between these two pairs of beards; such an edge would destroy the induced bone. In the applications in Claim 7 (after the correction above) and in Claim 9, the extra properties supplied by Algorithm 1 - namely that Y_i is stable and each beard has exactly one neighbor in X_{i-1} - do provide the required separation. The lemma as stated, however, is not valid for p=N without these additional hypotheses, so the statement should be amended to either exclude p=N or include the needed private-neighbor conditions.
  3. [Section 4, Theorem 1.8(2)] The equality case is internally inconsistent. The theorem statement says G is isomorphic to S^p_{n-1}; the proof initially asserts that S^p_{n-1} is the extremal graph; and the final sentence concludes that S^p_{n-2} is the unique deficiency-critical graph attaining the extremum. The discrepancy is not only typographical: for p=3 and even n, |V(S^p_{n-1})| = n^2 is even, while the claimed extremal deficiency n^2-3n+1 is odd, so that construction cannot have the stated deficiency. The authors should correct the subscript and verify the deficiency of the claimed extremal graph directly.
minor comments (4)
  1. [Abstract and Introduction] There are several typos, including 'is defines' for 'is defined' in the abstract and 'defines' in the definition of alpha_l. These should be fixed in a revision.
  2. [Algorithm 1, Remark] The remark following Algorithm 1 states a property with N(x+) cap X_i, while condition (3) of the algorithm itself uses N(u+) cap X_{i-1}; the index should be i-1 for consistency.
  3. [Remark to Theorem 1.9(1)] I do not find the alleged failure of K_{1,n}-freeness in the tightness construction E^p_{m-1,n-2}. The m-1 clique vertices are pairwise adjacent, so an induced star centered at a clique vertex can contain at most one of them, and the remaining leaves come from the n-2 pendant edges of its attached D^p copy; the resulting maximum is n-1 leaves, which is consistent with K_{1,n}-freeness.
  4. [Section 3, Claim 9] The notation x_N and x_{N+1} is used in the proof even though the path P_x has no vertices at levels N and N+1. This is harmless for nonexistent vertices, but the proof would be clearer if the convention for unused path indices were stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a self-contained combinatorial derivation from stated hypotheses.

full rationale

The paper derives its deficiency bounds entirely from internal definitions (levellings, snail horns, Algorithm 1, and the stated closure condition on the admitting set A). No parameter is fitted to a subset of the data and then renamed as a prediction; the matching algorithm is an existence argument, not a statistical fit. The central hypothesis in Theorem 1.4---that A consists of odd integers with p+q±1 not in A for p,q at least m---is used as an input to force contradictions when certain bone indices are produced by Lemma 2.9; the lemma itself is proved directly from the levelling structure and the definition of an admitting set, not imported from the authors' prior work. The extremal constructions (B S^n, T_{m,n}, S^p_n, T^p_n, E^p_{m,n}) are used only to show tightness, and their deficiency computations are independent of the upper-bound proof. There are no self-citations at all in this manuscript, so no self-citation chain is load-bearing. The proof is fully contained in the paper modulo standard graph-theoretic facts and the cited theorem of Fujita et al., which is used only as a motivation and starting point, not as the justification of the new bound. The skeptical note about the iterated private-neighbor index in Claim 7 concerns a possible typo or gap in the written proof (a correctness issue), not a circular reduction: it does not make the theorem's conclusion an equivalent reformulation of its assumptions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No constants are fitted; m, n, p, q, and A are theorem inputs. The proof is self-contained apart from standard graph-theoretic facts. The named objects (bone, snail horn, admitting set) are definitions, not entities requiring independent falsifiable evidence.

assumptions (3)
  • standard math All graphs are finite and simple.
    Section 1, first sentence; every matching and induced-subgraph argument assumes this.
  • standard math In a levelling from a fixed root, an edge joins vertices whose levels differ by at most one.
    Used in induced-star counting and bone constructions, e.g., Claims 4 and 12; follows from the definition of distance levels.
  • domain assumption The admitted set A in G(A) is exactly the set of induced bone lengths, with no other forbidden structures unless explicitly stated.
    This defines the graph classes in Theorems 1.4, 1.8, and 1.9; added K3 or Km restrictions are explicit hypotheses.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Induced subgraphs of graphs with large deficiency." pith.science (2026). https://pith.science/paper/AYKJSJAY

@misc{pith2026250515149,
  author       = {Pith},
  title        = {Pith review of: Induced subgraphs of graphs with large deficiency},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AYKJSJAY}},
  note         = {Machine review of arXiv:2505.15149}
}
abstract

The deficiency of a graph $G$, denoted by $\kd(G)$, is the number of vertices not saturated by a maximum matching. A bone $B_i$ is the tree obtained by attaching two pendent edges to each of the end vertices of a path $P_{i}$. The local independence number of $G$, denoted by $\alpha_l(G)$, is defines as the maximum integer $t$ such that $G$ contains an induced star $K_{1,t}$. Motivated by the seminal works of Scott and Seymour~(2016), Chudnovsky et al. (2017, 2020) on finding special types of holes in graphs with large chromatic number and bounded clique number, we establish an analog result by finding special types of bones in graphs with large deficiency and bounded local independence number. Fujita et al. (2006) proved that $\kd(G)\le n-2$ if $G$ is a connected graph with $\alpha_l(G)<n$ and containing no bones. We further establish exact extremal deficiency bounds for connected graphs with bounded local independence number that exclude specific bone configurations. An algorithm that constructs large matchings and establishes an upper bound on the deficiency is also provided.

Figures

Figures reproduced from arXiv: 2505.15149 by the authors.

Figure 1
Figure 1. Graphs BSp n, Sp n, Tp n, Ep m,n and E p+ m,n. All edges exist between the two end of the thick blue line. The red vertex v is the vertex added to E p+ m,n from E p m,n. Remark: The upper bound def(G) ≤ m(n − 3)(n − 2) m−3 2 + 1 is asymptotically optimal with respect to the leading item (n − 3)(n − 2) m−3 2 , and when m = 3, the upper bound def(G) ≤ 2n − 5 is tight. The tightness of these upper bounds are shown in t… view at source ↗
Figure 2
Figure 2. F(a1, a2, a3): the dashed line represents path, the blue triangle in L0 ∪ La1 ∪ La2 means the K3 got by Y -∆ operation. large along with the increasing of m. Therefore, in order to bound the deficiency, we need additional restriction on the clique number ω(G). Construction C: For a graph G and a vertex v ∈ V (G) with neighborhood N(v) = {a, b, c}, a Y −∆ operation at v consists of replacing v with three new vertices… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

  1. [1]

    Excluding a clique or a biclique in graphs of bounded induced matching treewidth

    T. Abrishami, M. Briański, J. Czyżewska, R. McCarty, M. Mi lanič, P. Rzążewski, and B. Walczak, Excluding a clique or a biclique in graphs of bound ed induced matching treewidth, arXiv:2405.04617

    work page Pith review arXiv

  2. [2]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, K4-free graphs with no odd holes, J. Combin. Theory Ser. B. 100 (2010) 313–331

    work page 2010

  3. [3]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour, Proof of a conjecture of Plu mmer and Zha, J. Graph Theory. 103 (2023) 437–450

    work page 2023

  4. [4]

    Chudnovsky, A

    M. Chudnovsky, A. Scott and P. Seymour, Induced subgraph s of graphs with large chromatic number. III. Long holes, Combinatorica 37 (2017) 1057-1072

    work page 2017

  5. [5]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, P. Seymour and S. Spirkl, Induce d subgraphs of graphs with large chromatic number. VIII. Long odd holes. J. Combin. The ory Ser. B 140 (2020) 84-97. 25

    work page 2020

  6. [6]

    Dallard, M

    C. Dallard, M. Krnc, O. Kwon, M. Milanič, A. Munaro, K. Što rgel and S. Wiederrecht, Treewidth versus clique number. IV. Tree-independence num ber of graphs excluding an induced star, arXiv:2402.11222

    arXiv

  7. [7]

    A survey of degree-boundedness

    X. Du and R. McCarty, a survey of degree-boundedness, arX iv:2403.05737v2

    work page Pith review arXiv

  8. [8]

    Dallard, M

    C. Dallard, M. Milanič and K. Štorgel, Treewidth versus c lique number. I. Graph classes with a forbidden structure, SIAM J. Discrete Math. 35 (2021), no. 4, 2618–2646

    work page 2021

Show all 18 references
  1. [9]

    Fujita, K

    S. Fujita, K. Kawarabayashi, C. L. Lucchesi, K. Ota, M. Pl ummer and A. Saito. A pair of forbidden subgraphs and perfect matchings. J. Combin. Th eory Ser. B 96, (2006) 315–324

    2006

  2. [10]

    A. Gyárfás, Problems from the world surrounding perfec t graphs, in: Proceedings of the Inter- national Conference on Combinatorial Analysis and i ts Applications, Pokrzywna, 1985, Zastos. Mat. 19 (1987) 413–441

    1987

  3. [11]

    Gyárfás and M

    A. Gyárfás and M. Zaker, On (δ, χ)-bounded families of graphs, Electron. J. Combin. 18 (2011), no. 1, Paper 108, 8 pp

    2011

  4. [12]

    Jünger, W

    M. Jünger, W. R. Pulleyblank and G. Reinelt. On partitio ning the edges of graphs into connected subgraphs, J. Graph Theory 9 (1985) 539-549

    1985

  5. [13]

    Las Vergnas

    M. Las Vergnas. A note on matchings in graphs, Colloque s ur la Théorie des Graphes (Paris 1974), Cahiers Centre Études Rech. Opér. 17 (1975) 257-260

    1975

  6. [14]

    D. P. Sumner. 1-factors and antifactor sets, J. London Math. Soc. 13 (1976) 351-359

    1976

  7. [15]

    Schiermeyer and B

    I. Schiermeyer and B. Randerath, Polynomial χ-binding functions and forbidden in- duced subgraphs: a survey, Graphs Combin. 35 (2019), no. 1, 1–31

    2019

  8. [16]

    Scott and P

    A. Scott and P. Seymour, Induced subgraphs of graphs wit h large chromatic number. I. Odd holes, J. Combin. Theory Ser. B 121 (2016) 68-84

    2016

  9. [17]

    Scott and P

    A. Scott and P. Seymour, A survey of χ-boundedness, J. Graph Theory 95 (2020), no. 3, 473–504

    2020

  10. [18]

    D. Wu, B. G. Xu and Y. Xu, The chromatic number of heptagrap hs, J. Graph Theory 106 (2024), no. 3, 711–736. 26

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.