%0 Journal Article %1 courcelle2020unified %A Courcelle, Bruno %A Durand, Irène %A Raskin, Michael %D 2020 %K finiteautomata graphexploration informal preprint %T A unified algorithm for colouring graphs of bounded clique-width. %X Clique-width is one of the graph complexity measures leading to polynomial special-case algorithms for generally NP-complete problems, e.g. graph colourability. The best two currently known algorithms for verifying c-colourability of graphs represented as clique-width terms are optimised towards two different extreme cases, a constant number of colours and a very large number of colours. We present a way to unify these approaches in a single relatively simple algorithm that achieves the state of the art complexity in both cases. The unified algorithm also provides a speed-up for a large number of colours.

@article{courcelle2020unified, abstract = {Clique-width is one of the graph complexity measures leading to polynomial special-case algorithms for generally NP-complete problems, e.g. graph colourability. The best two currently known algorithms for verifying c-colourability of graphs represented as clique-width terms are optimised towards two different extreme cases, a constant number of colours and a very large number of colours. We present a way to unify these approaches in a single relatively simple algorithm that achieves the state of the art complexity in both cases. The unified algorithm also provides a speed-up for a large number of colours.}, added-at = {2020-10-01T17:09:33.000+0200}, author = {Courcelle, Bruno and Durand, Irène and Raskin, Michael}, biburl = {https://www.bibsonomy.org/bibtex/2f79926892d9f772c6bdaa4398d7f6183/paves}, interhash = {3224afc57f268c925b20aa4a9cfad044}, intrahash = {f79926892d9f772c6bdaa4398d7f6183}, keywords = {finiteautomata graphexploration informal preprint}, note = {http://arxiv.org/abs/2008.07468}, timestamp = {2023-09-24T19:11:28.000+0200}, title = {A unified algorithm for colouring graphs of bounded clique-width.}, year = 2020 }