A certifying algorithm for 3-colorability of P5-free graphs

2009/07/20 by Bruce, Daniel, Hoang, Chinh T., Sawada, Joe
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0907.3497

Abstract

We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colorable and minimal with respect to this property.

Related

• k-Colorability of P5-free graphs
• Deciding k-colourability of P₅-free graphs in polynomial time
• P=NP
• Polynomial-time algorithm for vertex k-colorability of P₅-free graphs
• Certifying coloring algorithms for graphs without long induced paths