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?
Your problem is equivalent to maximum matching. In an optimal coloring, each color class is connected. Choosing one edge from each color class, we get a matching. This shows that the maximum matching is at least the antichromatic number. In the other direction, take any maximal matching, and color each of the pairs using a different color. Every other vertex is adjacent to some colored vertex (otherwise the matching isn't maximal), so you can extend this to an antichromatic coloring, showing that the antichromatic number is at least the size of a maximum matching.
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.
