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 \rightarrow \mathbb{N}\) such that \(f(v) \neq f(w)\) if \(v\) is adjacent to \(w\). Given a graph \(G = (V, E)\) and a function \(\gamma: V \rightarrow \mathbb{N}\), \(G\) is \(\mu\)-colorable if it admits a coloring \(f\) with \(f(v) \leq \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.