Vertex-critical (P5,chair)-free and (P5,cricket)-free graphs
Discrete Mathematics · 2027-03 · 350 (3) · 115515
DOI: 10.1016/j.disc.2026.115515 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2027-03. Verfasst von Jorik Jooken. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Research Foundation Flanders.
Abstract (Originalsprache)
For graphs $G, F_1$ and $F_2$, we say that $G$ is $(F_1,F_2)$-free if neither $F_1$ nor $F_2$ is an induced subgraph of $G$. We say that $G$ is $k$-vertex-critical if the chromatic number of $G$ is $k$, but every proper induced subgraph of $G$ has chromatic number at most $k-1$. The $\textit{chair}$ graph is a $5$-vertex graph obtained by adding a pendant vertex to one of the two central vertices of a path on $4$ vertices. The $\textit{cricket}$ graph is a $5$-vertex graph obtained by adding two pendant vertices to a common vertex of a triangle. The path on $5$ vertices is denoted by $P_5$. We prove that for every $k \geq 1$, there are only finitely many $(P_5,\text{chair})$-free $k$-vertex-critical graphs. We also prove that the same conclusion holds if $\text{chair}$ is replaced by $\text{cricket}$. We further characterize all $5$-vertex-critical $(P_5,\text{chair})$-free graphs, all $5$-vertex-critical $(P_5,\text{cricket})$-free graphs and all $6$-vertex-critical $(P_5,\text{cricket})$-free graphs. Our proofs rely on bounding the size of antichains and developing Ramsey-theoretic ideas. For any fixed integer $k \geq 1$, our results imply the existence of a polynomial time algorithm to decide whether a $(P_5,\text{chair})$-free (or $(P_5,\text{cricket})$-free) graph is $(k-1)$-colourable such that this algorithm can also present a negative constant-size certificate in case the graph is not $(k-1)$-colourable.
Förderung
- Research Foundation Flanders
Zitieren
APA
Jooken, J. (2027). Vertex-critical (P5,chair)-free and (P5,cricket)-free graphs. Discrete Mathematics, 350(3), 115515. https://doi.org/10.1016/j.disc.2026.115515
Vancouver
Jooken J. Vertex-critical (P5,chair)-free and (P5,cricket)-free graphs. Discrete Mathematics. 2027;350(3):115515. doi:10.1016/j.disc.2026.115515
BibTeX
@article{Jooken2027,
author = {Jooken, Jorik},
title = {Vertex-critical (P5,chair)-free and (P5,cricket)-free graphs},
journal = {Discrete Mathematics},
year = {2027},
volume = {350},
number = {3},
pages = {115515},
doi = {10.1016/j.disc.2026.115515}
}
EUVIMED