Narrowing the Complexity Gap for Colouring ($C_s$,$P_t$)-Free Graphs

Shenwei Huang, Matthew Johnson, Daniël Paulusma

For a positive integer $k$ and graph $G=(V,E)$, a $k$-colouring of $G$ is a mapping $c:V\to \{1,2,\dots ,k\}$ such that $c(u)\ne c(v)$ whenever $uv\in E$. The $k$-Colourin…