Backbone colouring of chordal graphs

Júlio Araújo, Nicolas Nisse, Lucas Picasarri-Arrieta

A proper $k$-colouring of a graph $G=(V,E)$ is a function $c:V(G)\to \{1,\dots ,k\}$ such that $c(u)\ne c(v)$ for every edge $uv\in E(G)$. The chromatic number $\chi (G)$ is the mini…