# Anti-chromatic number

What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its neighbour vertices?

Is there anything in literature about this variant of coloring?

-

This problem is equivalent to finding a minimum edge cover for the given graph. Each edge in the edge cover corresponds to a pair of adjacent nodes that are the same color. The edges involved in a minimum edge cover make up a subgraph in which each component is a tree (if any component contained a cycle, at least one edge could be removed); and clearly each component must be monochromatic. Since a tree with $n_i$ nodes has $2n_i-1$ edges, it's clear that a set of $k$ disjoint trees with $n$ total nodes has $2n-k$ edges. Inverting the relation, we see that if the minimum edge cover of an $n$-node graph has $m$ edges, then it has $k=2n-m$ components. At most $2n-m$ different colors may be used without violating your "anti-chromatic" constraint.