RECORD
A dichotomy for the number of vertex-critical ($P_5$, $H$)-free graphs when $H$ is bipartite
Combinatorics · Submitted 20 Aug 2026
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge 5$ , there are only finitely many $k$-vertex-critical $(P_5,H)$-free graphs if and only if $H$ is $2P_2$-free.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge 5$ , there are only finitely many $k$-vertex-critical $(P_5,H)$-free graphs if and only if $H$ is $2P_2$-free. This leads us to pose the problem about determining for which graphs $H$ with $\chi(H)\ge 3$ there are infinitely many $k$-vertex-critical $(P_5,H)$-free graphs for all $k\ge 5$. Toward this problem, we show that there only finitely many $k$-vertex-critical $(P_5, K_{s,t}+e)$-free graphs for all $k,s,t\ge 1$, where $K_{s,t}+e$ is a complete bipartite graph plus a single edge. On the other hand, we show that there are infinitely many $k$-vertex-critical $(P_5,\operatorname{net},\operatorname{co-net},\overline{C_5},\overline{C_6},\dots\overline{C_{k-1}})$-free graphs for all $k\ge 5$. We also show that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,\overline{L(K_{2,n})})$-free graphs for all $\ell,n\ge 0$, providing the largest known subfamily of $(P_4+\ell P_1)$-free graphs to satisfy this property. Our results, together with known results, imply the existence of new polynomial-time certifying algorithms to determine the $k$-colourability of many subfamilies of $P_5$-free and $(P_4+\ell P_1)$-free graphs for fixed $k\ge 5$. Our proof techniques apply a powerful theorem of Chudnovsky, Kim, Oum, and Seymour (2016) on prime graphs that we expect to be of interest and have further applications to bounding the number of $k$-vertex-critical graphs in other hereditary families of graphs.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. | background 1.00 | 0.07 | 0.02 | asserted 0.99 |
| s1 | A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge 5$ , there are only finitely many $k$-vertex-critical $(P_5,H)$-free graphs if and only if $H$ is $2P_2$-free. | result 0.91 | 0.93 | 0.92 | asserted 1.00 |
| s2 | This leads us to pose the problem about determining for which graphs $H$ with $\chi(H)\ge 3$ there are infinitely many $k$-vertex-critical $(P_5,H)$-free graphs for all $k\ge 5$. | future work 0.73 | 0.31 | 0.04 | unclear 0.38 |
| s3 | Toward this problem, we show that there only finitely many $k$-vertex-critical $(P_5, K_{s,t}+e)$-free graphs for all $k,s,t\ge 1$, where $K_{s,t}+e$ is a complete bipartite graph plus a single edge. | result 0.94 | 0.95 | 0.06 | asserted 1.00 |
| s4 | On the other hand, we show that there are infinitely many $k$-vertex-critical $(P_5,\operatorname{net},\operatorname{co-net},\overline{C_5},\overline{C_6},\dots\overline{C_{k-1}})$-free graphs for all $k\ge 5$. | result 0.98 | 0.96 | 0.07 | asserted 1.00 |
| s5 | We also show that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,\overline{L(K_{2,n})})$-free graphs for all $\ell,n\ge 0$, providing the largest known subfamily of $(P_4+\ell P_1)$-free graphs to satisfy this property. | result 0.98 | 0.95 | 0.06 | asserted 1.00 |
| s6 | Our results, together with known results, imply the existence of new polynomial-time certifying algorithms to determine the $k$-colourability of many subfamilies of $P_5$-free and $(P_4+\ell P_1)$-free graphs for fixed $k\ge 5$. | interpretation 0.97 | 0.81 | 0.17 | asserted 0.98 |
| s7 | Our proof techniques apply a powerful theorem of Chudnovsky, Kim, Oum, and Seymour (2016) on prime graphs that we expect to be of interest and have further applications to bounding the number of $k$-vertex-critical graphs in other hereditary families of graphs. | method 0.93 | 0.55 | 0.04 | asserted 0.52 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge 5$ , there are only finitely many $k$-vertex-critical $(P_5,H)$-free graphs if and only if $H$ is $2P_2$-free. This leads us to pose the problem about determining for which graphs $H$ with $\chi(H)\ge 3$ there are infinitely many $k$-vertex-critical $(P_5,H)$-free graphs for all $k\ge 5$. Toward this problem, we show that there only finitely many $k$-vertex-critical $(P_5, K_{s,t}+e)$-free graphs for all $k,s,t\ge 1$, where $K_{s,t}+e$ is a complete bipartite graph plus a single edge. On the other hand, we show that there are infinitely many $k$-vertex-critical $(P_5,\operatorname{net},\operatorname{co-net},\overline{C_5},\overline{C_6},\dots\overline{C_{k-1}})$-free graphs for all $k\ge 5$. We also show that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,\overline{L(K_{2,n})})$-free graphs for all $\ell,n\ge 0$, providing the largest known subfamily of $(P_4+\ell P_1)$-free graphs to satisfy this property. Our results, together with known results, imply the existence of new polynomial-time certifying algorithms to determine the $k$-colourability of many subfamilies of $P_5$-free and $(P_4+\ell P_1)$-free graphs for fixed $k\ge 5$. Our proof techniques apply a powerful theorem of Chudnovsky, Kim, Oum, and Seymour (2016) on prime graphs that we expect to be of interest and have further applications to bounding the number of $k$-vertex-critical graphs in other hereditary families of graphs.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 5 sentences without a confident label
Cites as background 2 papers
-
* chair or cricket [ref] * $P_5$ [ref] * $P_3+P_2$ or gem [ref] * dart [ref] * $K_1,3+P_1$ or $K_3+2P_1$ [ref] * $W_4$ [ref] * bull [ref]
Structural description of (bull, house)-free graphs · Introduction · 0.86
-
* chair or cricket [ref] * $P_5$ [ref] * $P_3+P_2$ or gem [ref] * dart [ref] * $K_1,3+P_1$ or $K_3+2P_1$ [ref] * $W_4$ [ref] * bull [ref]
Vertex-critical $(P_5,\text{chair})$-free and $(P_5,\text{cricket})$-free graphs · Introduction · 0.86
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.