Between Coloring and List-Coloring: $\mu$-coloring

Abstract

A new variation of the coloring problem, $\mu$-coloring, is defined in this paper. A coloring of a graph $G=(V,E)$ is a function $f:V\to \mathbb{N}$ such that $f(v)\ne f(w)$ if $v$ is adjacent to $w$. Given a graph $G=(V,E)$ and a function $\gamma :V\to \mathbb{N}$, $G$ is $\mu$-colorable if it admits a coloring $f$ with $f(v)\le \mu (v)$ for each $v\in V$. It is proved that $\mu$-coloring lies between coloring and list-coloring, in the sense of generalization of problems and computational complexity. Furthermore, the notion of perfection is extended to $\mu$-coloring, giving rise to a new characterization of cographs. Finally, a polynomial time algorithm to solve $p$-coloring for cographs is shown.