On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring

Julio Araujo, Alexandre A. Cezar, Ana Silva

A proper $k$-coloring 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 $uv\in E(G)$. The chromatic number $\chi (G)$ is the minimum $…