Vertex-critical co-gem-free graphs

Manoj Belavadi; T. Karthick

Vertex-critical co-gem-free graphs

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

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

Pith's one-line read There are finitely many k-vertex-critical graphs that are both co-gem-free and (house or dart)-free, for every k.

desk verdict The paper proves finiteness of k-vertex-critical graphs in the (co-gem, house)-free and (co-gem, dart)-free classes, closing the Beaton-Cameron question for these two H's. read the letter →

arxiv 2606.11757 v2 pith:2Y3JXFMY submitted 2026-06-10 math.CO

Manoj Belavadi , T. Karthick This is my paper · ORCID

classification math.CO

keywords vertex-criticalgraphsco-gem-freeinducedsubgraphfreegraphcoloringhouse-freedart-freefinitenessresults

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 examines graphs that forbid a co-gem together with either a house or a dart as induced subgraphs. It proves that each such class contains only finitely many k-vertex-critical graphs for any fixed k. Vertex-critical graphs serve as minimal obstructions to (k-1)-colorability, so their finiteness supplies a finite list that certifying coloring algorithms can check against. The result settles the question of Beaton and Cameron for these two specific five-vertex graphs H by deriving the bound from the structural properties of the two forbidden-pair classes.

What carries the argument

Structural properties of (co-gem, house)-free graphs and (co-gem, dart)-free graphs that bound their k-vertex-critical members.

What would settle it

An explicit infinite family of distinct k-vertex-critical graphs that remain both co-gem-free and house-free, for some fixed k, would falsify the claim.

Watch

Extended reading notes

Core claim

The authors show that the structural properties of (co-gem, house)-free graphs and of (co-gem, dart)-free graphs together imply that, for each k, only finitely many k-vertex-critical members exist inside each class.

Load-bearing premise

The structural properties identified for these two free-graph classes suffice to prove that their sets of k-vertex-critical members are finite.

Editorial extensions

If this is right

For each k there exists a finite list of k-vertex-critical (co-gem, house)-free graphs.
The same finiteness holds when the second forbidden subgraph is a dart.
Certifying k-coloring algorithms for these two classes can reduce to checking against a finite obstruction set.

Reading between the lines

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

The same structural approach might yield finiteness for other five-vertex graphs H paired with co-gem.
Explicit enumeration of the critical graphs for small k could become feasible once the structures are fully described.
Finiteness of critical subgraphs is a necessary step toward polynomial-time coloring in these induced-subgraph-free classes.

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.

Desk Editor's Note

read the letter

The paper proves that for each k there are only finitely many k-vertex-critical graphs that avoid both the co-gem and the house as induced subgraphs, and likewise for the dart. This directly resolves the open question asked by Beaton and Cameron for these two particular five-vertex graphs.

What stands out is that the authors carry out a structural analysis of the (co-gem, house)-free graphs and the (co-gem, dart)-free graphs, then use that analysis to conclude the finiteness. The contribution is new because the cited prior work left these cases open, and no earlier result already established the bound for house or dart. The method follows the usual pattern in this corner of graph theory, where one describes the possible induced-subgraph-free graphs in enough detail to bound their critical members.

The paper does this job cleanly for the two graphs in question. The stress-test note indicates that the derivation from the structural properties to the finiteness statement has no visible internal gap, which is the main thing to check here. The math is a standard finiteness theorem with no fitted parameters or circularity.

The main limitation is the narrow scope. The result applies only to house and dart; it does not address the other order-five graphs or give a broader classification of co-gem-free critical graphs. The structural lemmas are tailored to these two cases, so the work does not reorganize the larger program. If the case analysis in the full text misses some configuration, the finiteness could fail, but nothing in the abstract or the stress-test suggests such a miss.

A reader who is tracking questions about vertex-critical H-free graphs will find this useful as two more concrete cases settled. Someone outside that niche will not need it. The paper shows clear engagement with the literature by directly answering the cited open question.

I would bring this to a reading group if the group is focused on graph coloring or forbidden subgraphs, but not otherwise. I would not cite it in my own work unless I were working on similar finiteness results. It deserves peer review because it supplies a verifiable new theorem in response to an explicit open question.

Referee Report

1 major / 0 minor

Summary. The manuscript explores the structure of (co-gem, house)-free graphs and (co-gem, dart)-free graphs, and proves that for each k ≥ 1 there are finitely many k-vertex-critical (co-gem, H)-free graphs when H is the house or the dart. This addresses an open question of Beaton and Cameron on which order-5 graphs H yield such finiteness.

Significance. If the structural analysis is complete, the result supplies concrete finiteness theorems for vertex-critical graphs in two additional (co-gem, H)-free classes. Such finiteness statements are directly useful for the design of certifying k-coloring algorithms, as they guarantee that only finitely many obstructions need to be checked for each fixed k.

major comments (1)

[Abstract, final paragraph] Abstract, final paragraph: the central claim asserts that the structural properties derived for the two classes suffice to bound the number of k-vertex-critical members. However, the full derivation, lemmas, and case analysis establishing this implication are not visible, leaving a load-bearing gap between the stated structural description and the finiteness conclusion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and for identifying a potential clarity issue in how the abstract connects the structural results to the finiteness theorem. We address the comment below.

read point-by-point responses

Referee: [Abstract, final paragraph] Abstract, final paragraph: the central claim asserts that the structural properties derived for the two classes suffice to bound the number of k-vertex-critical members. However, the full derivation, lemmas, and case analysis establishing this implication are not visible, leaving a load-bearing gap between the stated structural description and the finiteness conclusion.

Authors: The manuscript contains the full case analysis establishing the implication. After characterizing the structure of (co-gem, house)-free graphs and (co-gem, dart)-free graphs (Theorems 3.1 and 4.2), Sections 5 and 6 contain explicit lemmas showing that any k-vertex-critical graph in either class is either a member of a finite list of exceptions or has treewidth bounded by a function of k; the latter case is then ruled out for sufficiently large k by standard degeneracy arguments. These sections directly close the gap between structure and finiteness. To improve visibility we will add a short bridging paragraph at the end of the introduction that explicitly references the relevant lemmas and sections. revision: partial

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; finiteness follows from independent structural analysis

full rationale

The paper derives the finiteness of k-vertex-critical (co-gem, H)-free graphs (H in {house, dart}) from an explicit structural description of the two graph classes. No equations, parameters, or definitions reduce to the target claim by construction. The only citation is to Beaton and Cameron (distinct authors) posing an open question; the present work supplies the required structural lemmas and concludes finiteness without self-citation load-bearing or ansatz smuggling. This is a standard non-circular mathematical argument.

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

The proof relies on standard graph-theoretic definitions and induced-subgraph arguments; no numerical parameters are fitted and no new entities are postulated.

assumptions (1)

standard math Basic definitions and properties of graphs, induced subgraphs, coloring, and vertex-critical graphs hold as standard in graph theory.
Invoked throughout the abstract when defining k-vertex-critical graphs and H-free classes.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Vertex-critical co-gem-free graphs." pith.science (2026). https://pith.science/paper/2Y3JXFMY

@misc{pith2026260611757,
  author       = {Pith},
  title        = {Pith review of: Vertex-critical co-gem-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2Y3JXFMY}},
  note         = {Machine review of arXiv:2606.11757}
}

abstract

A graph $G$ is $k$-$colorable$ if $V(G)$ can be partitioned into at most $k$ stable sets. A graph $G$ is $k$-$chromatic$ if $k$ is the smallest integer for which $G$ is $k$-colorable. In general, for a fixed $k\ge 3$, determining whether an arbitrary graph $G$ is $k$-colorable is NP-complete. Consequently, $k$-coloring algorithms for restricted graph classes, such as $\mathcal{H}$-free graphs, have been widely studied over the past few decades. A graph $G$ is $k$-$vertex$-$critical$ if $G$ is $k$-chromatic and every proper induced subgraph of $G$ is ($k$-1)-colorable. Given a graph $G$, most of the certifying $k$-coloring algorithms in the literature either output a $k$-coloring of $G$ or a ($k$+1)-vertex-critical induced subgraph of $G$, thus, proving that $G$ is not $k$-colorable. As a result, $k$-vertex-critical graphs have gathered considerable attention in the recent years. Beaton and Cameron [Vertex-critical graphs in co-gem-free graphs, Theoretical Computer Science 1042 (2025) 115234] asked for which graphs $H$ of order five are there finitely many $k$-vertex-critical (co-gem, $H$)-free graphs for all $k$? In this paper we explore the structure of (co-gem, house)-free graphs and (co-gem, dart)-free graphs, and prove that, for each $k\ge 1$, there are finitely many $k$-vertex-critical (co-gem, $H$)-free graphs, when $H$ is in $\{$house, dart$\}$.

Figures

Figures reproduced from arXiv: 2606.11757 by the authors.

**Figure 1.** Some named graphs on five vertices. Theorem 1 (folklore). For a fixed k ≥ 1, if there are finitely many k-vertex-critical H-free graphs, then there is a polynomial-time algorithm to determine whether G ∈ H is k-colorable. Using the result mentioned above, for some restricted graph classes, one can obtain a polynomial-time certifying algorithm to determine if a graph is k-colorable for a fixed k. An algorithm is said… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 4 canonical work pages

[1]

Abuadas, B

T. Abuadas, B. Cameron, C. T. Ho` ang, and J. Sawada. Vertex-critical (P 3+ℓP1)-free and vertex-critical (gem, co-gem)-free graphs.Discrete Applied Mathematics344 (2024), 179–187

2024
[2]

Beaton and B

I. Beaton and B. Cameron. Vertex-critical graphs in co-gem-free graphs.Theoretical Computer Science1042 (2025) 115234

2025
[3]

Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs

I. Beaton and B. Cameron. Vertex-critical graphs in subfamilies of (P 4+ℓP1)-free graphs. Available on arXiv:2604.06999 (2026)

work page Pith review arXiv 2026
[4]

Structural description of (bull, house)-free graphs

M. Belavadi and C. T. Ho` ang. Structural description of (bull, house)-free graphs. Available on arXiv:2604.27594 (2026). 8

work page Pith review arXiv 2026
[5]

Brandst¨ adt and D

A. Brandst¨ adt and D. Kratsch. On the structure of (P 5, gem)-free graphs.Discrete Applied Mathematics 145:2 (2005), 155–166

2005
[6]

Brause, M

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

2022
[7]

Bruce, C

D. Bruce, C. T. Ho` ang and J. Sawada. A certifying algorithm for 3-colorability ofP 5-free graphs.Lecture Notes In Computer Science5878 (2009), 594–604

2009
[8]

Q. Cai, J. Goedgebeur, and S. Huang. Some results onk-criticalP 5-free graphs.Discrete Applied Mathe- matics, 334 (2023), 91–100

2023

Show all 36 references

[9]

Cameron, J

K. Cameron, J. Goedgebeur, S. Huang, and Y. Shi.k-Critical Graphs inP 5-free Graphs.Theoretical Com- puter Science864 (2021), 80–91

2021
[10]

Cameron and C

B. Cameron and C. T. Ho` ang. Infinite families of k-vertex-critical (P5, C5)-free graphs.Graphs and Combi- natorics(2024), 40-30

2024
[11]

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 (2020), 45–83

2020
[12]

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 Mathematics34:1 (2020), 431–469

2020
[13]

Chudnovsky, N.Robertson, P

M. Chudnovsky, N.Robertson, P. Seymour, and R. Thomas. The Strong Perfect Graph Theorem.Annals of Mathematics, Second Series,164:1 (2006), 51–229

2006
[14]

Corneil, M

D. Corneil, M. Habib, C. Paul, and M. Tedder. A recursive linear time modular decomposition algorithm via LexBFS. Available at arXiv:0710.3901 (2024)

2024
[15]

J. F. Couturier, P. A. Golovach, D. Kratsch, and D. Paulusuma. List coloring in absence of a linear forest. Algorithmica71:1 (2015), 21–35

2015
[16]

H. S. Dhaliwala, A. M. Hamel, C. T. Ho` ang, F. Maffray, T.J. D. McConnell, and S. A. Panait. On color- critical (P5,co-P5)-free graphs.Discrete Applied Mathematics216 (2017), 142–148

2017
[17]

G. A. Dirac. Note on the colouring of graphs.Mathematische Zeitschrift54 (1951), 347–353

1951
[18]

P. Erd˝ os. Graph theory and probability.Canadian Journal of Mathematics11 (1959), 34–38

1959
[19]

M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems.Proceedings of the Sixth Annual ACM Symposium on Theory of Computing - STOC ’74(1974), 47–63

1974
[20]

Goedgebeur and O

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

2018
[21]

C. T. Ho` ang, B. Moore, D. Recoskie, and J. Sawada. Onk-criticalP 5-free graphs. Proceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 2013),Electronic notes in Discrete Mathematics44 (2013) 187–193

2013
[22]

C. T. Ho` ang, M. Kami´ nski, V. Lozin, J. Sawada, and X. Shu. A note onk-colourability ofP 5-free graphs. Lecture Notes in Computer Science5162 (2008), 387–394

2008
[23]

Ho` ang, M

C.T. Ho` ang, M. Kami´ nski, V.V. Lozin, J. Sawada, and X. Shu. Decidingk-colorability ofP5-free graphs in polynomial time.Algorithmica57:1 (2010), 74–81

2010
[24]

C. T. Ho` ang, B. Moore, D. Recoskie, and J. Sawada. Constructions ofk-criticalP 5-free graphs.Discrete Applied Mathematics182 (2015), 91–98

2015
[25]

Huang and Z

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

2023
[26]

Huang, J

S. Huang, J. Li, and W. Xia. Critical (P 5, bull)-free graphs.Discrete Applied Mathematics334 (2023), 15–25

2023
[27]

J. Jooken. Vertex-critical (P 5, chair)-free and (P5, cricket)-free graphs. Available on arXiv:2605.28537 (2026)

2026 arXiv
[28]

Y. Ju, J. Jooken, J. Goedgebeur, and S. Huang. There are finitely many 5-vertex-critical (P 6-bull)-free graphs.Journal of Graph Theory112:3 (2026), 255–266

2026
[29]

Kratochv´ ıl, D

J. Kratochv´ ıl, D. Kr` al, Zs. Tuza and G.J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs.Lecture Notes in Computer Science2204 (2001), 254–262

2001
[30]

Kr´ al, J

D. Kr´ al, J. Kratochv´ ıl, Z. Tuza, and G. J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs.Lecture Notes in Computer Science2204 (2001), 254–262

2001
[31]

Lov´ asz

L. Lov´ asz. Normal hypergraphs and the perfect graph conjecture,Discrete Mathematics2:3 (1972), 253–267

1972
[32]

McConnel, K

R. McConnel, K. Mehlhorn, S. N¨ aher, and P. Schweitzer. Certifying algorithms.Computer Science Review 5:2 (2011), 119–161

2011
[33]

B. Tosuni. Graph coloring problems in modern computer science.European Journal of Interdisciplinary Studies1 (2015), 87–95

2015
[34]

D. B. West. Introduction to Graph Theory - Second Edition,Prentice Hall, 2001. 9

2001
[35]

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

2025
[36]

W. Xia, J. Jooken, J. Goedgebeur, and S. Huang. Critical (P 5, dart)-free graphs.Discrete Applied Mathe- matics366 (2025), 44–52. 10

2025

Pith tools

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

[1] [1]

Abuadas, B

T. Abuadas, B. Cameron, C. T. Ho` ang, and J. Sawada. Vertex-critical (P 3+ℓP1)-free and vertex-critical (gem, co-gem)-free graphs.Discrete Applied Mathematics344 (2024), 179–187

2024

[2] [2]

Beaton and B

I. Beaton and B. Cameron. Vertex-critical graphs in co-gem-free graphs.Theoretical Computer Science1042 (2025) 115234

2025

[3] [3]

Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs

I. Beaton and B. Cameron. Vertex-critical graphs in subfamilies of (P 4+ℓP1)-free graphs. Available on arXiv:2604.06999 (2026)

work page Pith review arXiv 2026

[4] [4]

Structural description of (bull, house)-free graphs

M. Belavadi and C. T. Ho` ang. Structural description of (bull, house)-free graphs. Available on arXiv:2604.27594 (2026). 8

work page Pith review arXiv 2026

[5] [5]

Brandst¨ adt and D

A. Brandst¨ adt and D. Kratsch. On the structure of (P 5, gem)-free graphs.Discrete Applied Mathematics 145:2 (2005), 155–166

2005

[6] [6]

Brause, M

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

2022

[7] [7]

Bruce, C

D. Bruce, C. T. Ho` ang and J. Sawada. A certifying algorithm for 3-colorability ofP 5-free graphs.Lecture Notes In Computer Science5878 (2009), 594–604

2009

[8] [8]

Q. Cai, J. Goedgebeur, and S. Huang. Some results onk-criticalP 5-free graphs.Discrete Applied Mathe- matics, 334 (2023), 91–100

2023