Deciding k-colourability of $P_5$-free graphs in polynomial time
<|reference_start|>Deciding k-colourability of $P_5$-free graphs in polynomial time: 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$-free graph admits a $k$-colouring, for each fixed number of colours $k$, can be done in polynomial time. If such a colouring exists, our algorithm produces it.<|reference_end|>
@article{hoàng2007deciding,
    title={Deciding k-colourability of $P_5$-free graphs in polynomial time},
    author={Ch'inh T. Ho`ang, Marcin Kami'nski, Vadim Lozin, J. Sawada, X. Shu},
    journal={arXiv preprint arXiv:cs/0702043},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0702043},
    primaryClass={cs.DS}
}