A Characterization of Claw-Free Graphs using Zero Forcing Invariants

Ben Small; Houston Schuerger; Randy Davila

REVIEW 3 major objections 4 minor 1 cited by

A Characterization of Claw-Free Graphs using Zero Forcing Invariants

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

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

Pith's one-line read The paper proves that every connected claw-free graph has equal standard and positive semidefinite zero forcing numbers, and that this equality on all induced subgraphs characterizes claw-free graphs.

desk verdict A clean conjecture-resolution with an elegant forcing-set argument, but the main proof leans on a lemma it states, cites, and then overclaims. read the letter →

arxiv 2412.03463 v2 pith:HA325EWQ submitted 2024-12-04 math.CO

Randy Davila , Houston Schuerger , Ben Small This is my paper · ORCID

classification math.CO MSC 68R10

keywords claw-freegraphspositivesemidefinitezeroforcingstandardpathbundles(Z+Z)-perfectgraphcharacterization

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

Zero forcing is a graph coloring game: start with a set of blue vertices and spread the blue color under a precise rule, and the zero forcing number is the smallest starting set that eventually colors every vertex. This paper proves that for every connected claw-free graph, the standard rule and the more flexible positive semidefinite rule need the same number of starting vertices. The result confirms a conjecture put forward by a computer conjecturing program, and it completes a characterization: a graph has the two numbers equal in every induced subgraph exactly when it contains no induced claw $K_{1,3}$. Equality matters because the two numbers bound different nullity parameters for matrices whose zero pattern follows the graph, so the theorem identifies a structural class where those linear-algebra bounds coincide.

What carries the argument

The engine is the path bundle of a relaxed chronology, where a relaxed chronology is a schedule of the simultaneous forces applied at each time step: for a fixed vertex $x$, follow the component containing $x$ at each step and record the chain of forces that eventually color $x$; the terminus of the restricted forcing sequence inside that bundle is again a positive semidefinite forcing set. Lemma 3 and Lemma 4 use this fact to show that any connected graph has a minimum positive semidefinite forcing set $S$ whose complement $G-S$ is connected. The main proof then runs an induction: from such an $S$, the set of remaining white vertices stays connected after every force, because a disconnection would produce an induced claw centered at the vertex just forced. That connectedness is the mechanism that upgrades each positive semidefinite force to a standard force, transferring the minimum set from one rule to the other.

What would settle it

Exhaustively compute $Z$ and $Z_+$ for all connected claw-free graphs on at most ten vertices; a single graph with $Z_+(G) < Z(G)$ would disprove the theorem.

Watch

Extended reading notes

Core claim

The central claim is that the inequality $Z_+(G)\le Z(G)$, true for every graph, becomes an equality on claw-free graphs, where a claw $K_{1,3}$ is a vertex joined to three pairwise nonadjacent vertices. The paper proves the stronger structural fact that every connected graph has a minimum positive semidefinite forcing set whose complement is connected. Starting from such a set, claw-freeness forces the white vertices to stay connected throughout the forcing process; if a forced vertex ever separated its remaining white neighbors, those neighbors and the forcing vertex would form an induced claw. Connected white vertices turn every legal positive semidefinite force into a legal standard force, so the same minimum set works for both rules. Consequently a graph is $(Z_+,Z)$-perfect, meaning $Z_+(H)=Z(H)$ for every induced subgraph $H$, if and only if it is claw-free.

Load-bearing premise

The whole proof depends on the already-proved fact that the terminus of a path-bundle restriction is itself a positive semidefinite forcing set; if that fact failed, the construction of a minimum forcing set with connected complement would break, and the main equivalence would be unsupported.

Editorial extensions

If this is right

For any connected claw-free graph, the minimum sizes of the two forcing sets coincide, so computing either invariant gives the other.
A graph has $Z_+(H)=Z(H)$ for every induced subgraph $H$ if and only if it is claw-free; any graph containing an induced $K_{1,3}$ is witnessed by that subgraph, which has $Z_+=1$ and $Z=2$.
The equality extends to disconnected claw-free graphs by additivity over components, and it sharpens the previously known two-sided bounds to an exact value on this class.
The structural lemmas guarantee that every connected graph has a minimum positive semidefinite forcing set whose complement is connected; on claw-free graphs this set is automatically a standard forcing set.

Reading between the lines

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

Beyond the paper, the connected-complement lemma is likely reusable: any forcing rule whose legal moves depend only on the component of the uncolored subgraph should admit the same minimum-set-with-connected-complement construction, opening the same equality proof for other invariants.
Beyond the paper, the equality of the two numbers suggests the full forcing processes coincide on claw-free graphs, so propagation time and other timing parameters under the two rules are natural objects to compare.
Beyond the paper, the characterization has a computational flavor: a constructive version of the cited path-bundle terminus result would turn a minimum positive semidefinite forcing set on a claw-free graph into a minimum standard forcing set, giving an algorithm for $Z$ on this class.

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.

Desk Editor's Note

read the letter

Short version: this paper looks like it settles the TxGraffiti conjecture that Z and Z+ coincide on claw-free graphs, and the corollary (claw-free iff every induced subgraph has Z=Z+) is a nice bonus. I think the result is true and the proof strategy is good, but there is a real gap in Section 3 that needs to be closed before I'd trust the argument as written.

What's new: the theorem itself. Previous work had equality for line graphs and general bounds for claw-free graphs. Here they prove full equality and, as a consequence, a hereditary characterization. The induction in Theorem 5 is clean: once you have a minimum PSD forcing set whose complement is connected, claw-freeness forces every PSD force to be a standard force, so the set is also a standard forcing set. The idea behind Lemma 4—iteratively enlarge a component of the complement of a min forcing set until it's connected—is neat, and the component-enlargement argument in Lemma 3 is intricate but credible.

The soft spot is Lemma 2 and its use in Lemma 3. Lemma 2 is stated as a citation to [5], an in-press paper by overlapping authors, and it is not proved here. In the proof of Lemma 3, after constructing S' as the terminus of the path bundle, the text says 'By Lemma 2, S' is a minimum positive semidefinite forcing set.' But the Lemma 2 stated in this manuscript only says the terminus is a positive semidefinite forcing set, not that it has minimum size. That is a genuine gap. It is plausible that the path bundle has one terminus per initial blue vertex, so |S'|=|S|, but that is not stated or proved. If that cardinality fact is true, the proof goes through; if not, Lemma 4 and Theorem 5 are unsupported. This is not just a presentation gripe—it's a load-bearing missing argument.

I'd suggest the authors prove Lemma 2 in the paper, or at least state and prove the cardinality preservation explicitly. Relying on an in-press paper for this step is uncomfortable, even if the cited paper is legitimate.

Who this is for: people working on zero forcing invariants and structural graph theory. It deserves a serious referee. I'd recommend sending it out, with a request to fix the Lemma 2/minimality issue before acceptance.

Referee Report

3 major / 4 minor

Summary. The paper proves that for every connected claw-free graph G, the standard zero forcing number Z(G) equals the positive semidefinite zero forcing number Z_+(G), confirming a conjecture attributed to the program TxGraffiti. The proof strategy is to first establish, via a sequence of lemmas, that every connected graph admits a minimum positive semidefinite forcing set whose complement is connected (Lemma 4), and then to show that any positive semidefinite forcing process starting from such a set can be replayed as a standard forcing process, using claw-freeness to prevent the white subgraph from disconnecting. As a corollary, the authors characterize (Z_+,Z)-perfect graphs as exactly the claw-free graphs.

Significance. If the main theorem is correct, it resolves a natural conjecture and provides a clean structural characterization of graphs for which two important zero forcing parameters coincide on every induced subgraph. The inductive argument in Theorem 5 is elegant and self-contained once Lemma 4 is granted, and the corollary is immediate. The paper also contributes an auxiliary structural result of independent interest (Lemma 4) about the existence of minimum positive semidefinite forcing sets with connected complement. However, the proof of Lemma 4 depends critically on Lemma 2, which is imported without proof from an in-press paper by overlapping authors, and the use made of Lemma 2 in the proof of Lemma 3 is stronger than the statement as written. This is a genuine correctness risk that must be addressed before the result can be considered fully established.

major comments (3)

[Section 3, Lemma 3 proof] The sentence 'By Lemma 2, S' is a minimum positive semidefinite forcing set of G' does not follow from Lemma 2 as stated. Lemma 2 asserts only that Term(F|Q(F;x)) is a positive semidefinite forcing set; it says nothing about minimal cardinality. To justify that S' is minimum, one needs to prove that |Term(F'|Q(F';w*))| = |S|, for example by showing that the path bundle contains exactly one terminal vertex per initial blue vertex and that these terminals are distinct. This cardinality statement is plausible but is neither stated nor proved. Since Lemma 4 and hence Theorem 5 rely on S' being a minimum forcing set, this is a load-bearing gap. The authors should either prove the needed cardinality property, or state and prove a stronger version of Lemma 2 that includes minimality, or provide a fully accessible proof of Lemma 2 itself.
[Section 3, Lemma 3 proof, final containment] The claim that 'S'∩ V(C) = ∅' is justified only by the phrase 'as S' is the terminus of the restricted forces in G[V(C^0_w*)∪S].' This is not a complete argument. A precise proof should show that the path bundle Q(F';w*) is contained in V(C^0_w*)∪S, and hence its terminus is also contained in that set, which is disjoint from V(C). Without this, the conclusion that V(C) is properly contained in a component of G−S' is not fully established. This issue is secondary to the cardinality gap but still needs to be addressed for a rigorous proof.
[Section 3, Lemma 2 citation] Lemma 2 is the engine of the paper's main structural result, yet it is stated as a citation to an in-press paper [5] that includes two of the present authors and is not publicly available. The present manuscript does not provide a proof, nor does it give a preprint link. For a referee to verify the main theorem, the statement of Lemma 2 must be either proved in this paper or made available with enough detail to check the stronger version needed in Lemma 3. I recommend that the authors include a proof or an explicit derivation, at least in an appendix, to make the paper self-contained.

minor comments (4)

[General] The proof of Theorem 5 is well structured and the claw-free argument in the inductive step is convincing. The paper would benefit from a short discussion of why the path bundle has exactly one terminal per initial blue vertex, which would also help clarify the use of Lemma 2.
[Section 1] In the abstract and introduction, 'claw-free graphs offer a complete characterization of (Z_+,Z)–perfect graphs' is stated before the corollary; consider moving this interpretation to the conclusion to avoid overclaiming before the result is proved.
[Section 4, Corollary 6 proof] The phrase 'way of contraposition' should be 'by way of contraposition'.
[Title page] The email address of Houston Schuerger is typeset incorrectly as 'schuerger h@utpb.edu' with an extra space.

Circularity Check

1 steps flagged · score 4.0 of 10

The main theorem's proof is not circular, but its pivotal Lemma 4 rests on Lemma 2, a load-bearing self-citation to an overlapping-authors paper that is not proved here.

self citation load bearing [Section 3, Lemma 2 and proof of Lemma 3 (supporting Lemma 4 and Theorem 5)]
"Lemma 2 ([5]). Let G be a graph, and let B be a positive semidefinite forcing set of G. If F is a relaxed chronology of forces for B on G, and Q is the path bundle of F induced by some vertex x∈ V (G), then the set Term(F|Q(F ;x)) is a positive semidefinite forcing set of G. ... By Lemma 2, S′ is a minimum positive semidefinite forcing set of G."

Lemma 4, which Theorem 5 explicitly invokes, is proved by repeatedly applying Lemma 3, and Lemma 3's construction of the new set S' ends with 'By Lemma 2, S' is a minimum positive semidefinite forcing set of G.' Lemma 2 is not proved in this paper; it is stated as a citation to [5], whose author list includes two of the present authors (Schuerger and Small) and which is 'to appear.' The stated Lemma 2 only says the terminus is a positive semidefinite forcing set, not that it is minimum; the proof of Lemma 3 silently uses the stronger cardinality property. Thus a load-bearing step in the main derivation is supported by an overlapping-authors citation plus an unstated inference rather than by the definitions in this paper.

full rationale

The paper's central claim, Z+(G)=Z(G) for connected claw-free graphs, is not a renaming, a fit, or a definitional identity: after Lemma 4 the proof gives a genuine induction showing that every positive semidefinite force from a minimum forcing set with connected complement is a valid standard force, using only the claw-free condition and the definitions of the two color-change rules. Corollary 6 then follows cleanly from Theorem 5 plus the known values on K1,3. No parameter is fitted to data, no prediction is a disguised input, and no uniqueness theorem is invoked to forbid alternatives. The only significant concern is structural dependence: Lemma 4 relies on Lemma 3, and Lemma 3 relies on Lemma 2, which is imported without proof from [5], a paper by overlapping authors. The printed statement of Lemma 2 does not contain the 'minimum' property that Lemma 3 needs, so the derivation has a gap and a load-bearing self-citation. This is a correctness and provenance risk, not a circular reduction of the theorem to its assumptions; if the missing cardinality observation is supplied and [5]'s path-bundle lemma is accepted, the rest of the proof is self-contained. Score 4 reflects load-bearing self-citation with independent central content.

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

The paper derives the main result from definitions, standard facts, and one nontrivial lemma from prior work. No free parameters or invented entities appear.

assumptions (4)

domain assumption Lemma 2: for any graph G, PSD forcing set B, relaxed chronology F, and path bundle Q(F;x), the terminus Term(F|Q(F;x)) is a PSD forcing set of G.
Stated in Section 3 and cited to [5], an in-press paper by overlapping authors. It is essential for constructing a minimum forcing set with connected complement in Lemma 3.
standard math Z and Z+ are additive over connected components.
Used before Corollary 6 to extend Theorem 5 from connected to arbitrary claw-free graphs. Standard in zero forcing literature.
standard math Any PSD forcing process can be represented as a chronological list with one force per time step.
Used in Lemma 3 and Theorem 5 to reason about a single force at each step; standard and implicit.
standard math Z+(G) is at most Z(G) for every graph G.
Used at the start of Theorem 5; follows immediately because PSD forces are more flexible than standard forces.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Characterization of Claw-Free Graphs using Zero Forcing Invariants." pith.science (2026). https://pith.science/paper/HA325EWQ

@misc{pith2026241203463,
  author       = {Pith},
  title        = {Pith review of: A Characterization of Claw-Free Graphs using Zero Forcing Invariants},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HA325EWQ}},
  note         = {Machine review of arXiv:2412.03463}
}

abstract

We prove that the \emph{standard zero forcing number} $Z(G)$ and the \emph{positive semidefinite zero forcing number} $Z_+(G)$ are equal for all claw-free graphs $G$. This result resolves a conjecture proposed by the computer program \emph{TxGraffiti} and highlights a connection between these graph invariants in claw-free structures. As a corollary, we show that a graph $G$ is claw-free if and only if every induced subgraph $H \subseteq G$ satisfies $Z(H) = Z_+(H)$.

Figures

Figures reproduced from arXiv: 2412.03463 by the authors.

**Figure 2.** An example illustrating the construction of a path bundle ind [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

In Reverie Together: Ten Years of Mathematical Discovery with a Machine Collaborator
cs.DM 2025-07 conditional novelty 7.0 of 10 partial

Four machine-generated open conjectures relating independence, zero forcing, domination, and matching invariants in graphs are presented, each with empirical support but no proof.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages · cited by 1 Pith paper

[5]

Hogben, M

L. Hogben, M. Hunnell, K. Liu, H. Schuerger, B. Small, and Y. Zhang, New structures and their applications to variants of zero forcing and propagation ti me, Electron. J. Comb. (to appear.)

work page
[1]

428 (2008), no

AIM Minimum Rank – Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628–1648

work page 2008
[2]

Barioli, W

F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben , B. Shader, P. van Hieu, and M. Young, Parameters related to tree-width, zero forcing, and maximu m nullity of a graph , J. Graph Theory 72 (2013), no. 2, 146–177

work page 2013
[3]

Davila, Automated conjecturing in mathematics with TxGraﬃti, Discov

R. Davila, Automated conjecturing in mathematics with TxGraﬃti, Discov. Artif. Intell. (to appear.)

work page
[4]

Fallat and A

S. Fallat and A. Soltani, Line graphs: their maximum nullities and zero forcing number s, Czech. Math. J. 66 (2016), no. 4, 743–755

work page 2016
[6]

Hogben, J

L. Hogben, J. C.-H. Lin, and B. L. Shader, Inverse problems and zero forcing for graphs , Mathematical Surveys and Monographs, vol. 265, American Ma thematical Society, 2022. 8

work page 2022
[7]

Wang and B

L. Wang and B. Yang, Positive semideﬁnite zero forcing numbers of two classes of graphs, Theor. Comput. Sci. 786 (2019), 44–54

work page 2019
[8]

D. B. West, Introduction to graph theory , second ed., Prentice Hall, September 2000. 9

work page 2000

Pith tools

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

[1] [5]

Hogben, M

L. Hogben, M. Hunnell, K. Liu, H. Schuerger, B. Small, and Y. Zhang, New structures and their applications to variants of zero forcing and propagation ti me, Electron. J. Comb. (to appear.)

work page

[2] [1]

428 (2008), no

AIM Minimum Rank – Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628–1648

work page 2008

[3] [2]

Barioli, W

F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben , B. Shader, P. van Hieu, and M. Young, Parameters related to tree-width, zero forcing, and maximu m nullity of a graph , J. Graph Theory 72 (2013), no. 2, 146–177

work page 2013

[4] [3]

Davila, Automated conjecturing in mathematics with TxGraﬃti, Discov

R. Davila, Automated conjecturing in mathematics with TxGraﬃti, Discov. Artif. Intell. (to appear.)

work page

[5] [4]

Fallat and A

S. Fallat and A. Soltani, Line graphs: their maximum nullities and zero forcing number s, Czech. Math. J. 66 (2016), no. 4, 743–755

work page 2016

[6] [6]

Hogben, J

L. Hogben, J. C.-H. Lin, and B. L. Shader, Inverse problems and zero forcing for graphs , Mathematical Surveys and Monographs, vol. 265, American Ma thematical Society, 2022. 8

work page 2022

[7] [7]

Wang and B

L. Wang and B. Yang, Positive semideﬁnite zero forcing numbers of two classes of graphs, Theor. Comput. Sci. 786 (2019), 44–54

work page 2019

[8] [8]

D. B. West, Introduction to graph theory , second ed., Prentice Hall, September 2000. 9

work page 2000