EUVIMEDEUVIMED entdecken
Crossref

There Are Finitely Many 5‐Vertex‐Critical (P6,bull)‐Free Graphs

Yiao Ju, Jorik Jooken, Jan Goedgebeur, Shenwei Huang

Journal of Graph Theory · 2026-07 · 112 (3) · 255-266

DOI: 10.1002/jgt.70027 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 23.03.2026. Verfasst von Yiao Ju und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 18 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we are interested in 4‐colouring algorithms for graphs that do not contain an induced path on six vertices nor an induced bull, that is, the graph with vertex set and edge set . Such graphs are referred to as ‐free graphs. A graph is ‐ vertex‐critical if , and every proper induced subgraph of has . In the current paper, we investigate the structure of 5‐vertex‐critical ‐free graphs and show that there are only finitely many such graphs, thereby answering a question of Maffray and Pastor. A direct corollary of this is that there exists a polynomial‐time algorithm to decide if a ‐free graph is 4‐colourable such that this algorithm can also provide a certificate that can be verified in polynomial time and serves as a proof of 4‐colourability or non‐4‐colourability.

Zitieren

APA

Ju, Y., Jooken, J., Goedgebeur, J., & Huang, S. (2026). There Are Finitely Many 5‐Vertex‐Critical (P6,bull)‐Free Graphs. Journal of Graph Theory, 112(3), 255-266. https://doi.org/10.1002/jgt.70027

Vancouver

Ju Y, Jooken J, Goedgebeur J, Huang S. There Are Finitely Many 5‐Vertex‐Critical (P6,bull)‐Free Graphs. Journal of Graph Theory. 2026;112(3):255-266. doi:10.1002/jgt.70027

BibTeX
@article{Ju2026,
  author = {Ju, Yiao and Jooken, Jorik and Goedgebeur, Jan and Huang, Shenwei},
  title = {There Are Finitely Many 5‐Vertex‐Critical (P6,bull)‐Free Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {112},
  number = {3},
  pages = {255--266},
  doi = {10.1002/jgt.70027}
}
Kostenlos starten →