Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 13 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.