Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

Konrad K. Dabrowski, Francois Dross, Matthew Johnson +1

A colouring of a graph $G=(V,E)$ is a function $c:V\to \{1,2,\dots \}$ such that $c(u)\ne c(v)$ for every $uv\in E$. A $k$-regular list assignment of $G$ is a function $L…