An arXiv preprint reports an exact dividing line for a central counting question in graph theory: when H is bipartite and k is at least 5, the class of k-vertex-critical graphs that are (P5,H)-free is finite exactly when H is 2P2-free. If that condition on H fails, the same result places the class on the infinite side.
The paper studies k-vertex-critical graphs and hereditary graph classes specified by forbidden induced subgraphs. In plain terms, it looks at graph families formed by ruling out particular patterns when they occur as induced subgraphs, and asks whether only finitely many critical graphs remain at a given colouring level.
This is a theoretical study, not an analysis of a sampled population. Its objects are prime graphs, vertex-critical graphs and hereditary graph classes; no human, animal, laboratory or observational dataset is involved.
The rule has a sharp edge
The headline dichotomy is deliberately narrow and exact. For a bipartite forbidden graph H covered by the statement, the answer is determined by one structural property: whether H is 2P2-free. The result distinguishes the finite and infinite cases within the (P5,H)-free setting rather than identifying only selected examples.
The preprint adds several finite cases outside that single yes-or-no formulation. For all positive k and n, only finitely many k-vertex-critical graphs are both P5-free and Hn-free.
It also proves finiteness for graphs that are both (P4 + ℓP1)-free and L(K2,n)-free, for every nonnegative ℓ and every positive k and n.
Another theorem covers the class of k-vertex-critical graphs that are (P5,Ks,t+e)-free. The paper states finiteness for all positive k and s, with t at least 2.
Where infinity persists
The other side is not left as an abstract possibility. For every k at least 5, the paper constructs infinitely many k-vertex-critical graphs avoiding the cycles C4 through Ck−1. These examples provide an explicit infinite family under the stated cycle restrictions.
Two further constructions give infinitely many k-vertex-critical graphs that are P5-free and net-free for k at least 5, and infinitely many k-vertex-critical graphs that are P5-free and co-net-free for the same range.
Taken together, the finite theorems and infinite constructions map a clear boundary: some carefully specified hereditary classes admit only finitely many critical graphs, while others support unending families.
A proof about structure, not sampling
The proof strategy is structural. A central finiteness lemma reduces the problem to bounding the order—the size—of colourable prime graphs in hereditary classes.
The paper then applies a theorem on unavoidable induced subgraphs in large prime graphs as a proof tool. In this argument, the issue is whether a sufficiently large prime graph must contain a pattern that conflicts with the class being studied.
That approach lets the paper turn properties of forbidden patterns into statements about how many critical graphs a class can contain. The conclusion is a collection of finiteness and infinitude theorems, rather than a statistical estimate or an observed rate.
Two concrete counts
The paper also reports exhaustive generation for two classes of 5-vertex-critical graphs. One class contains 287 graphs in the reported count, while the other contains 188.
Those totals are enumeration results, not estimates from a statistical sample. The supplied analysis notes that the reported material does not include full generation settings, a software version or an independently reproducible computational protocol, so the counts are best read as the preprint’s reported exhaustive totals.
The algorithmic implication has limits
The finiteness results also carry an algorithmic consequence: they imply the existence of many polynomial-time certifying k-Colouring algorithms for the stated hereditary subclasses.
That is an existence claim about algorithms, not a report of software performance. The study does not show that the proposed colouring algorithms were implemented or benchmarked in practice, and it provides no empirical validation on external graph datasets or real-world networks.
The open edge of the map
The result settles the bipartite test stated for k at least 5, but it does not extend the same conclusion to every forbidden graph outside that setting. The authors propose a conjecture for forbidden graphs with chromatic number exactly 3, characterizing those for which the relevant critical-graph class would be finite for all k at least 5.
That conjecture signals where the theory goes next: the exact criterion is complete for the bipartite case covered by the theorem, while broader non-bipartite cases remain separate questions. The supplied analysis specifically cautions that finiteness is not established for every non-bipartite H with chromatic number at least 3.
The supplied document is an arXiv version 1 preprint dated 20 August 2026. It presents mathematical results about graph families, while its algorithmic implications and computational counts remain within the scope of the results reported there.
Paper data and sources
Original title: A dichotomy for the number of vertex-critical ($P_5$, $H$)-free graphs when $H$ is bipartite
Authors: Iain Beaton, Ben Cameron
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text