2022/12/09 by Ben Cameron, Chı́nh T. Hoàng, Cameron, Ben +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2212.04659
openalex publication_date 2022/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a new, stronger proof that there are only finitely many k-vertex-critical (P5,~gem)-free graphs for all k. Our proof further refines the structure of these graphs and allows for the implementation of a simple exhaustive computer search to completely list all 6- and 7-vertex-critical (P5, gem)-free graphs. Our results imply the existence of polynomial-time certifying algorithms to decide the k-colourability of (P5, gem)-free graphs for all k where the certificate is either a k-colouring or a (k+1)-vertex-critical induced subgraph. Our complete lists for k≤ 7 allow for the implementation of these algorithms for all k≤ 6.