2015/06/11 by Jan Goedgebeur, Oliver Schaudt, Goedgebeur, Jan +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1506.03647
openalex publication_date 2015/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe an algorithm for generating all k-critical \mathcal H-free graphs, based on a method of Hoàng et al. Using this algorithm, we prove that there are only finitely many 4-critical (P7,Ck)-free graphs, for both k=4 and k=5. We also show that there are only finitely many 4-critical graphs (P8,C4)-free graphs. For each case of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. Moreover, we prove that for every t, the class of 4-critical planar Pt-free graphs is finite. We also determine all 27 4-critical planar (P7,C6)-free graphs. We also prove that every P10-free graph of girth at least five is 3-colorable, and determine the smallest 4-chromatic P12-free graph of girth five. Moreover, we show that every P13-free graph of girth at least six and every P16-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.