Deciding k-colourability of $P_5$-free graphs in polynomial time

Chính T. Hoàng, Marcin Kamiński, Vadim Lozin +2

The problem of computing the chromatic number of a $P_5$-free graph is known to be NP-hard. In contrast to this negative result, we show that determining whether or not a $P_5$-fre…