Pith. sign in

REVIEW 1 major objections 1 cited by

Vertex-critical $(P_5,\text{chair})$-free and $(P_5,\text{cricket})$-free graphs

T0 review · 1 major / 0 minor · reviewed 2026-06-29 · grok-4.3

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

Pith's one-line read For any fixed k there are only finitely many k-vertex-critical graphs that avoid both P5 and the chair as induced subgraphs.

desk verdict Finiteness of k-critical graphs in the (P5,chair) and (P5,cricket) classes, plus explicit lists for k=5 and 6. read the letter →

arxiv 2605.28537 v1 pith:G5DYPYIO submitted 2026-05-27 math.CO

Jorik Jooken This is my paper · ORCID
classification math.CO
keywords vertex-criticalgraphsinducedsubgraphfreeP5-freechair-freecricket-freechromaticnumbergraphcoloringalgorithmsRamseytheory
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

The paper establishes that for every integer k at least 1, the collection of k-vertex-critical graphs containing neither P5 nor the chair as an induced subgraph is finite. The identical finiteness statement holds when the chair is replaced by the cricket. Because only finitely many such critical graphs exist, it becomes possible to decide in polynomial time whether any given graph from either class is (k-1)-colorable and, when it is not, to exhibit a constant-size certificate of non-colorability. The proofs proceed by showing that sufficiently large critical graphs in these classes must contain one of the three forbidden induced subgraphs, using bounds on the size of antichains together with Ramsey-theoretic arguments.

What carries the argument

Bounds on the size of antichains together with Ramsey-theoretic arguments that force any sufficiently large k-critical graph to contain P5, chair or cricket as an induced subgraph.

What would settle it

An explicit infinite family of distinct k-vertex-critical graphs that are simultaneously P5-free and chair-free, for some fixed k.

Watch

Extended reading notes

Core claim

We prove that for every k ≥ 1, there are only finitely many (P5,chair)-free k-vertex-critical graphs. The same conclusion holds if chair is replaced by cricket. We further characterize all 5-vertex-critical (P5,chair)-free graphs, all 5-vertex-critical (P5,cricket)-free graphs and all 6-vertex-critical (P5,cricket)-free graphs. Our proofs rely on bounding the size of antichains and developing Ramsey-theoretic ideas.

Load-bearing premise

That antichain bounds and Ramsey arguments are enough to guarantee that any large enough k-critical graph in these classes contains P5, chair or cricket as an induced subgraph.

Editorial extensions

If this is right

  • A polynomial-time algorithm decides whether a (P5,chair)-free graph is (k-1)-colorable.
  • The same algorithm returns a constant-size certificate when the input is not (k-1)-colorable.
  • All 5-vertex-critical (P5,chair)-free graphs are explicitly characterizable.
  • All 5-vertex-critical (P5,cricket)-free graphs and all 6-vertex-critical (P5,cricket)-free graphs are explicitly characterizable.

Reading between the lines

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

  • The same finiteness technique may succeed for other pairs of five-vertex forbidden subgraphs if comparable antichain bounds can be established.
  • The coloring problem for the broader class of (P5,chair)-free graphs reduces to checking a finite list of potential critical obstructions once k is fixed.
  • One could attempt to verify the result computationally for small k by enumerating all critical graphs up to the size bound implied by the Ramsey arguments.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 0 minor

Summary. The paper proves that for every k ≥ 1 there are only finitely many k-vertex-critical graphs that are (P5, chair)-free, and likewise when chair is replaced by cricket. It also gives explicit characterizations of all 5-vertex-critical graphs in both classes and of all 6-vertex-critical (P5, cricket)-free graphs. The proofs are said to proceed by bounding antichain sizes and applying Ramsey-theoretic arguments; the finiteness results are used to obtain polynomial-time algorithms that decide (k-1)-colorability of graphs in these classes and supply constant-size certificates when the answer is negative.

Significance. If the central claims hold, the work supplies strong structural information on vertex-critical graphs inside two concrete (P5, H)-free classes for small 5-vertex H. The finiteness statements immediately yield bounded-order critical graphs and therefore polynomial-time coloring algorithms with explicit negative certificates, which is a concrete algorithmic payoff. The small-k characterizations add concrete structural descriptions that can be checked directly.

major comments (1)
  1. [Abstract] Abstract: the claim that antichain-size bounds together with Ramsey-theoretic extraction suffice to force a P5, chair or cricket in any sufficiently large k-critical graph is the load-bearing step, yet the abstract supplies no indication of the concrete structural lemmas that would guarantee the Ramsey argument respects the minimum-degree and connectivity conditions imposed by k-criticality.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that antichain-size bounds together with Ramsey-theoretic extraction suffice to force a P5, chair or cricket in any sufficiently large k-critical graph is the load-bearing step, yet the abstract supplies no indication of the concrete structural lemmas that would guarantee the Ramsey argument respects the minimum-degree and connectivity conditions imposed by k-criticality.

    Authors: We agree that the abstract is concise and does not explicitly reference the structural lemmas that underpin the Ramsey arguments. In the body of the paper, we first prove (Theorem 3.1 and Corollary 3.3) that any antichain in a k-vertex-critical (P5, chair)-free graph has size bounded by a function of k alone; an analogous bound holds for the cricket case. These bounds are then combined with the standard properties that every k-critical graph has minimum degree at least k-1 and is (k-1)-connected. The resulting Ramsey extraction (Lemma 4.2 and Theorem 4.4) forces the appearance of P5 together with chair or cricket once the graph is large enough. To make the logical flow clearer from the abstract, we will revise the abstract to include a short clause indicating that the finiteness proofs rely on antichain bounds that are compatible with the degree and connectivity conditions of criticality. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: standard finiteness proof via antichain bounds and Ramsey arguments

full rationale

The paper is a pure existence proof in graph theory establishing that (P5,chair)-free and (P5,cricket)-free k-vertex-critical graphs are finite for each fixed k. It relies on bounding antichain sizes and Ramsey-theoretic extraction to force forbidden induced subgraphs in sufficiently large critical graphs. No equations, fitted parameters, predictions from data, or self-referential definitions appear. The central claim does not reduce by construction to its inputs, and no load-bearing self-citations or uniqueness theorems imported from prior author work are invoked. The derivation is self-contained against external graph-theoretic definitions and standard techniques.

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

The paper operates entirely inside standard graph theory; no new constants, entities, or ad-hoc assumptions beyond the usual definitions of induced subgraphs, chromatic number, and vertex-criticality are introduced.

assumptions (1)
  • standard math Standard axioms and definitions of graph theory (induced subgraphs, chromatic number, vertex-criticality).
    The entire development rests on these background definitions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Vertex-critical $(P_5,\text{chair})$-free and $(P_5,\text{cricket})$-free graphs." pith.science (2026). https://pith.science/paper/G5DYPYIO

@misc{pith2026260528537,
  author       = {Pith},
  title        = {Pith review of: Vertex-critical $(P_5,\textchair)$-free and $(P_5,\textcricket)$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G5DYPYIO}},
  note         = {Machine review of arXiv:2605.28537}
}
abstract

For graphs $G, F_1$ and $F_2$, we say that $G$ is $(F_1,F_2)$-free if neither $F_1$ nor $F_2$ is an induced subgraph of $G$. We say that $G$ is $k$-vertex-critical if the chromatic number of $G$ is $k$, but every proper induced subgraph of $G$ has chromatic number at most $k-1$. The $\textit{chair}$ graph is a $5$-vertex graph obtained by adding a pendant vertex to one of the two central vertices of a path on $4$ vertices. The $\textit{cricket}$ graph is a $5$-vertex graph obtained by adding two pendant vertices to a common vertex of a triangle. The path on $5$ vertices is denoted by $P_5$. We prove that for every $k \geq 1$, there are only finitely many $(P_5,\text{chair})$-free $k$-vertex-critical graphs. We also prove that the same conclusion holds if $\text{chair}$ is replaced by $\text{cricket}$. We further characterize all $5$-vertex-critical $(P_5,\text{chair})$-free graphs, all $5$-vertex-critical $(P_5,\text{cricket})$-free graphs and all $6$-vertex-critical $(P_5,\text{cricket})$-free graphs. Our proofs rely on bounding the size of antichains and developing Ramsey-theoretic ideas. For any fixed integer $k \geq 1$, our results imply the existence of a polynomial time algorithm to decide whether a $(P_5,\text{chair})$-free (or $(P_5,\text{cricket})$-free) graph is $(k-1)$-colourable such that this algorithm can also present a negative constant-size certificate in case the graph is not $(k-1)$-colourable.

Figures

Figures reproduced from arXiv: 2605.28537 by the authors.

Figure 1
Figure 1. A visualization of several graphs on 5 vertices. By combining the previously discussed results, we can see that the only cases of Question 2 that remain open for some integers k ≥ 5 are when F2 is one of the following five graphs: P4 + P1, C4 + P1, P3 + 2P1, K5 − e and K5. 2 Vertex-critical (P5, chair)-free graphs Let G be a graph, let v ∈ V (G) be a vertex and let X, Y ⊆ V (G) be two subsets of vertices. We write N… 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

  1. Vertex-critical co-gem-free graphs

    math.CO 2026-06 unverdicted novelty 6.0 of 10

    There are finitely many k-vertex-critical (co-gem, house)-free graphs and (co-gem, dart)-free graphs for every k ≥ 1.

Reference graph

Works this paper leans on

24 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [1]

    Abuadas, B

    T. Abuadas, B. Cameron, C. T. Hoàng and J. Sawada. Vertex-critical(P3 +ℓP 1)-free and vertex-critical(gem,co-gem)-free graphs.Discrete Applied Mathematics, 344:179–187, 2024

    2024

  2. [2]

    Beaton and B

    I. Beaton and B. Cameron. Vertex-critical graphs in subfamilies of(P4 +ℓP 1)-free graphs. In International Workshop on Combinatorial Algorithms, 2026

    2026

  3. [3]

    Structural description of (bull, house)-free graphs

    M. Belavadi and C. T. Hoàng. Structural description of(bull,house)-free graphs. arXiv:2604.27594 [math.CO], 2026

    work page Pith review arXiv 2026

  4. [4]

    Brause, M

    C. Brause, M. Geißer and I. Schiermeyer. Homogeneous sets, clique-separators, critical graphs and optimalχ-binding functions.Discrete Applied Mathematics, 320:211–222, 2022

    2022

  5. [5]

    Q. Cai, J. Goedgebeur and S. Huang. Some results onk-criticalP5-free graphs.Discrete Applied Mathematics, 334:91–100, 2023

    2023

  6. [6]

    Cameron, J

    K. Cameron, J. Goedgebeur, S. Huang and Y. Shi.k-Critical Graphs inP5-free Graphs.The- oretical Computer Science, 864:80–91, 2021

    2021

  7. [7]

    Cameron and C

    B. Cameron and C. T. Hoàng. Infinite families ofk-vertex-critical(P5, C5)-graphs.Graphs and Combinatorics, 40(30), 2024

    2024

  8. [8]

    Cameron, C

    B. Cameron, C. T. Hoàng and J. Sawada. Dichotomizingk-vertex-criticalH-free graphs forH of order four.Discrete Applied Mathematics, 312:106–115, 2022

    2022

Show all 24 references
  1. [9]

    Chudnovsky, J

    M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong. Obstructions for three-coloring graphs without induced paths on six vertices.Journal of Combinatorial Theory, Series B, 140:45–83, 2020

    2020

  2. [10]

    Chudnovsky, J

    M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong. Obstructions for three-coloring and list three-coloringH-free graphs.SIAM Journal on Discrete Mathematics, 34(1):431–469, 2020

    2020

  3. [11]

    Coolsaet, S

    K. Coolsaet, S. D’hondt and J. Goedgebeur. House of Graphs 2.0: A database of interesting graphs and more.Discrete Applied Mathematics, 325:97–107, 2023. Available athttps://ho useofgraphs.org

    2023

  4. [12]

    H. S. Dhaliwal, A. M. Hamel, C. T. Hoàng, F. Maffray, T. J. D. McConnell and S. A. Panait. On color-critical (P5, co-P5)-free graphs.Discrete Applied Mathematics, 216:142–148, 2017

    2017

  5. [13]

    P. Erdős. Graph theory and probability.Canadian Journal of Mathematics, 11:34–38, 1959

    1959

  6. [14]

    Goedgebeur and O

    J. Goedgebeur and O. Schaudt. Exhaustive generation ofk-criticalH-free graphs.Journal of Graph Theory, 87:188–207, 2018. 13

    2018

  7. [15]

    Goedgebeur, J

    J. Goedgebeur, J. Jooken, K. Okrasa, P. Rzążewski and O. Schaudt. Minimal Obstructions to C5-Coloring in Hereditary Graph Classes.Information and Computation, 105445, 2026

    2026

  8. [16]

    C. T. Hoàng, M. Kamiński, V. V. Lozin, J. Sawada and X. Shu. Decidingk-colorability of P5-free graphs in polynomial time.Algorithmica, 57:74–81, 2010

    2010

  9. [17]

    C. T. Hoàng, B. Moore, D. Recoskie, J. Sawada and M. Vatshelle. Constructions ofk-critical P5-free graphs.Discrete Applied Mathematics, 182:91–98, 2015

    2015

  10. [18]

    Huang and Z

    S. Huang and Z. Li. Vertex-critical(P 5,chair)-free graphs.Discrete Applied Mathematics, 341:9–15, 2023

    2023

  11. [19]

    Kamiński and A

    M. Kamiński and A. Pstrucha. Certifying coloring algorithms for graphs without long induced paths.Discrete Applied Mathematics, 261:258–267, 2019

    2019

  12. [20]

    J. Jooken. Computer-assisted graph theory: a survey. arXiv:2508.20825 [math.CO], 2025

    2025

  13. [21]

    F. P. Ramsey. On a problem of formal logic.Proceedings of the London Mathematical Society, 2(30):264–286, 1930

    1930

  14. [22]

    E. Sperner. Ein Satz über Untermengen einer endlichen Menge.Mathematische Zeitschrift, 27(1):544–548, 1928

    1928

  15. [23]

    W. Xia, J. Jooken, J. Goedgebeur and S. Huang. Some Results on Critical(P5, H)-free graphs. Theoretical Computer Science, 115411, 2025

    2025

  16. [24]

    W. Xia, J. Jooken, J. Goedgebeur and S. Huang. Critical(P 5,dart)-free graphs.Discrete Applied Mathematics, 366:44–52, 2025. 14

    2025

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.