The coloring problem for \P₅,P₅\-free graphs and \P₅,K_p-e\-free graphs is polynomial

2015/03/09 by Malyshev, D. S., Lobanova, O. O.
#05C15 #05C85 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1503.02550

Abstract

We show that determining the chromatic number of a \P₅,P₅\-free graph or a \P₅,K_p-e\-free graph can be done in polynomial time

Related

• Deciding k-colourability of P₅-free graphs in polynomial time
• Polynomial-time algorithm for vertex k-colorability of P₅-free graphs
• k-Colorability of P5-free graphs
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
• Polynomial Cases for the Vertex Coloring Problem