k-Colorability of P5-free graphs

2006/09/14 by C. T. Hoang, Hoang, C. T., J. Sawada +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0609083

arxiv created 2006/09/14 · arxiv updated 2009/12/01

Abstract

A polynomial time algorithm that determines for a fixed integer k whether or not a P5-free graph can be k-colored is presented in this paper. If such a coloring exists, the algorithm will produce a valid k-coloring.

Related

• Polynomial-time algorithm for vertex k-colorability of P₅-free graphs
• Deciding k-colourability of P₅-free graphs in polynomial time
• A certifying algorithm for 3-colorability of P5-free graphs
• The coloring problem for \P₅,P₅\-free graphs and \P₅,K_p-e\-free graphs is polynomial
• Exploring k-Colorability