Exhaustive generation of k‐critical H‐free graphs. Issue 2 (28th April 2017)

• Record Type: Journal Article
• Authors: Goedgebeur, Jan; Schaudt, Oliver
• Is Part Of: Journal of graph theory. Volume 87:Issue 2(2018)
• Page Start: 188
• Page End: 207
• Publication Date: 2017-04-28
• Subjects: automatic proof -- critical graph -- graph coloring -- H‐free graph -- graph generation; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22151
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We describe an algorithm for generating all k ‐critical H ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H ‐free, k ‐chromatic, and every H ‐free proper subgraph of G is ( k − 1 ) ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ( P 7, C k ) ‐free graphs, for both k = 4 and k = 5 . We also show that there are only finitely many 4‐critical ( P 8, C 4 ) ‐free graphs. For each 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. In addition, we prove a number of characterizations for 4‐critical H ‐free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4‐critical planar P t ‐free graphs is finite. We also determine all 52 4‐critical planar P 7 ‐free graphs. We also prove that every P 11 ‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P 12 ‐free graph of girth at least five. Moreover, we show that every P 14 ‐free graph of girth at least six and every P 17 ‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.