<p>This problem is equivalent to finding a <a href="http://en.wikipedia.org/wiki/Edge_cover" rel="nofollow">minimum edge cover</a> 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.</p>

CC BY-SA 3.0
2014-03-24T20:02:22.053Z
2014-03-24T20:02:22.053Z
mjqxxxx
<p>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.</p>

CC BY-SA 3.0
2014-03-24T20:06:34.903Z
2014-03-24T20:06:34.903Z
Yuval Filmus
<p>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?</p>

<p>Is there anything in literature about this variant of coloring?</p>

<graph-theory><graph-colouring>
Anti-chromatic number
ekayaaslan
# Anti-chromatic number

(Asked by: username_0 on 2014-03-24)

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?

**Tags:** graph-theory, graph-colouring


---

## 2 answers

### Answer by username_2 on 2014-03-24. Score: 14 | Accepted answer

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.


---

### Answer by username_1 on 2014-03-24. Score: 3

This problem is equivalent to finding a [minimum edge cover](http://en.wikipedia.org/wiki/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.


---

