Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915923880837120 |
|---|---|
| author | Beaton, Iain Cameron, Ben |
| author_facet | Beaton, Iain Cameron, Ben |
| contents | A graph $G$ is $k$-vertex-critical if $χ(G)=k$ but $χ(G-v)<k$ for all $v\in V(G)$. In this paper we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical graphs in the following subfamilies of $(P_4+\ell P_1)$-free graphs for all $k\ge 1$ and $\ell\ge 0$:
$\bullet$ $(P_4+\ell P_1,\text{chair})$-free graphs,
$\bullet$ $(P_4+\ell P_1,P_5,\text{bull})$-free graphs, and
$\bullet$ $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs.
In fact, all but the first of these are special cases of our general result that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,B_{4}(m),B_{3}(m)^{+})$-free graphs for all $k\ge 1$ and $\ell,m\ge 0$. Here $B_{n}(m)$ is the graph obtained from a path of order $n$ by identifying one of its leaves with the centre vertex of $K_{1,m}$ and $B_{n}(m)^{+}$ is the graph obtained by identifying an edge of $K_3$ with the edge of $B_{n}(m)$ with endpoints of degrees $2$ and $m$, respectively. Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of all graphs in these subfamilies for every fixed $k$.
We also show that $χ(G)\le \ell+2$ for all $(P_4+\ell P_1,K_3)$-free graphs and all $\ell\ge 0$, improving the previously known upper bound of $2\ell+2$ that followed from Randerath and Schiermeyer's 2004 result on $(P_t,K_3)$-free graphs. More generally, we provide a $χ$-bound in $O(\ell^{ω-1})$ for $(P_4+\ell P_1)$-free graphs which improves the bound of $(2\ell+2)^{ω-1}$ which followed from Gravier, Hoàng and Maffray in 2003 for $P_{t}$-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06999 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs Beaton, Iain Cameron, Ben Combinatorics Discrete Mathematics 05C15, 05C75 A graph $G$ is $k$-vertex-critical if $χ(G)=k$ but $χ(G-v)<k$ for all $v\in V(G)$. In this paper we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical graphs in the following subfamilies of $(P_4+\ell P_1)$-free graphs for all $k\ge 1$ and $\ell\ge 0$: $\bullet$ $(P_4+\ell P_1,\text{chair})$-free graphs, $\bullet$ $(P_4+\ell P_1,P_5,\text{bull})$-free graphs, and $\bullet$ $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs. In fact, all but the first of these are special cases of our general result that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,B_{4}(m),B_{3}(m)^{+})$-free graphs for all $k\ge 1$ and $\ell,m\ge 0$. Here $B_{n}(m)$ is the graph obtained from a path of order $n$ by identifying one of its leaves with the centre vertex of $K_{1,m}$ and $B_{n}(m)^{+}$ is the graph obtained by identifying an edge of $K_3$ with the edge of $B_{n}(m)$ with endpoints of degrees $2$ and $m$, respectively. Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of all graphs in these subfamilies for every fixed $k$. We also show that $χ(G)\le \ell+2$ for all $(P_4+\ell P_1,K_3)$-free graphs and all $\ell\ge 0$, improving the previously known upper bound of $2\ell+2$ that followed from Randerath and Schiermeyer's 2004 result on $(P_t,K_3)$-free graphs. More generally, we provide a $χ$-bound in $O(\ell^{ω-1})$ for $(P_4+\ell P_1)$-free graphs which improves the bound of $(2\ell+2)^{ω-1}$ which followed from Gravier, Hoàng and Maffray in 2003 for $P_{t}$-free graphs. |
| title | Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs |
| topic | Combinatorics Discrete Mathematics 05C15, 05C75 |
| url | https://arxiv.org/abs/2604.06999 |