There are finitely many 5-vertex-critical (P6, bull)-free graphs

作     者：Ju, Yiao Jooken, Jorik Goedgebeur, Jan Huang, Shenwei 

作者机构：College of Computer Science Nankai University Tianjin300071 China Tianjin Key Laboratory of Network and Data Security Technology Nankai University Tianjin300071 China Department of Computer Science KU Leuven Campus Kulak-Kortrijk Kortrijk8500 Belgium Department of Applied Mathematics Computer Science and Statistics Ghent University Ghent9000 Belgium School of Mathematical Sciences and LPMC Nankai University Tianjin300071 China 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2025年

核心收录：

主　　题：Polynomial approximation 

摘      要：In this paper, we are interested in 4-colouring algorithms for graphs that do not contain an induced path on 6 vertices nor an induced bull, i.e., the graph with vertex set {v1, v2, v3, v4, v5} and edge set {v1v2, v2v3, v3v4, v2v5, v3v5}. Such graphs are referred to as (P6, bull)-free graphs. A graph G is k-vertex-critical if χ(G) = k, and every proper induced subgraph H of G has χ(H) 6, bull)-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 (P6, bull)-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. © 2025, CC BY.