Critical $(P_5,W_4)$-Free Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915095620091904 |
|---|---|
| author | Xia, Wen Jooken, Jorik Goedgebeur, Jan Beaton, Iain Cameron, Ben Huang, Shenwei |
| author_facet | Xia, Wen Jooken, Jorik Goedgebeur, Jan Beaton, Iain Cameron, Ben Huang, Shenwei |
| contents | A graph $G$ is $k$-vertex-critical if $χ(G) = k$ but $χ(G-v)<k$ for all $v \in V(G)$. A graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor $H_2$. A $W_4$ is the graph consisting of a $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$.
We show that there are finitely many $k$-vertex-critical $(P_5,W_4)$-free graphs for all $k \ge 1$ and we characterize all $5$-vertex-critical $(P_5,W_4)$-free graphs. Our results imply the existence of a polynomial-time certifying algorithm to decide the $k$-colorability of $(P_5,W_4)$-free graphs for each $k \ge 1$ where the certificate is either a $k$-coloring or a $(k+1)$-vertex-critical induced subgraph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04923 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Critical $(P_5,W_4)$-Free Graphs Xia, Wen Jooken, Jorik Goedgebeur, Jan Beaton, Iain Cameron, Ben Huang, Shenwei Combinatorics A graph $G$ is $k$-vertex-critical if $χ(G) = k$ but $χ(G-v)<k$ for all $v \in V(G)$. A graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ nor $H_2$. A $W_4$ is the graph consisting of a $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. We show that there are finitely many $k$-vertex-critical $(P_5,W_4)$-free graphs for all $k \ge 1$ and we characterize all $5$-vertex-critical $(P_5,W_4)$-free graphs. Our results imply the existence of a polynomial-time certifying algorithm to decide the $k$-colorability of $(P_5,W_4)$-free graphs for each $k \ge 1$ where the certificate is either a $k$-coloring or a $(k+1)$-vertex-critical induced subgraph. |
| title | Critical $(P_5,W_4)$-Free Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.04923 |