A decision problem in graph coloring - MathOverflow

A decision problem in graph coloring

2010-07-08T07:36:15Z

It'll be great to get a pointer or answer to the following question:

What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily minimal) vertex coloring of the graph in which each color is used at least twice?

Answer by Falk Hüffner for A decision problem in graph coloring

2010-07-08T09:39:58Z

It is NP-hard, since you can reduce the standard graph coloring problem to this problem by adding a sufficient number of degree-0 vertices.

Answer by Jukka Suomela for A decision problem in graph coloring

2010-07-08T13:45:13Z

A simple observation: if the maximum degree Δ is at most n/2 − 1, then there exists an equitable colouring with at most Δ + 1 = n/2 colours, and each colour class has to contain at least two nodes.

Answer by domotorp for A decision problem in graph coloring

2010-07-08T20:42:08Z

This is NOW a complete answer. We can suppose that each color appears at most three times. Take the complement of the graph. Your question becomes equivalent to decide whether this graph has a perfect matching*, where we also allow triples (K_3) to be matched together. This problem WAS studied before:

Muse's answer gives a paper that has a reference to this paper that shows that this problem is in P, see the abstract or Lemma 1 and after:

P. Hell and D. G. Kirkpatrick: Packings by cliques and by finite families of graphs

Update: Ryan found an older paper proving the necessary result:

G. Cornuéjols, D. Hartvigsen, and W. Pulleyblank: Packing subgraphs in a graph

Answer by Muse for A decision problem in graph coloring

2010-07-09T10:03:25Z

I think I have found the answer. The problem is easy and the reference is the following paper:

portal.acm.org/citation.cfm?id=1518279

(The coloring problem is first phrased in terms of cliques in the complement graph)

Answer by Ryan Williams for A decision problem in graph coloring

2010-07-09T17:20:53Z

I think domotorp is correct; let me clarify his answer a bit.

Note if any color appears four times or more, we can "split" it into two colors and still use each color at least twice. Finding a proper coloring is equivalent to partitioning the node set into disjoint independent sets (each part is a color class). Hence when we take the complement of the graph, we are seeking a partition of the node set into disjoint cliques. As we may assume each of these cliques have at most three nodes, the problem becomes: pack edges and triangles in a graph such that all nodes are covered. Not only is this problem in P, but the version where we have to maximize the number of nodes covered is also in P. That is proved here:

G. Cornuéjols, D. Hartvigsen, and W. Pulleyblank. Packing subgraphs in a graph. Operations Research Letters, Volume 1, Issue 4, September 1982, Pages 139-143

Answer by Lucas K. for A decision problem in graph coloring

2010-07-09T23:43:30Z

Some thoughts.

I like the idea of inverting the graph. I think the problem can be converted, to coloring the (inverted) graph for which each color appears exactly twice, or just once but then only on selected vertices (a joker vertex).

If the original inverted graph contains a 3-clique, then one of the vertices of the clique can be selected and be allowed (but not necessarily) to be colored with a color not appearing anywhere else in the graph. You can repeat this step, until the graph does not contain any 3-clique anymore, that does not have a selected vertex. I think it is not difficult to prove that a coloring in the converted problem can be used to construct a coloring in the original problem and vice versa.

With the converted problem, you eliminate any vertex that has 1 or 2 edges. In case of 1 edge, you remove the vertex and its neighbor. In case of 2 edges, you contract. By contraction, you can create a new 3-clique. However, in the converted problem, you are not allowed to color that with one color (that is why the conversion is necessary, because it allows the contraction).

A cycle with an odd number of vertices, will end up in a single vertex, in which it becomes clear that a coloring is not possible. But not all impossible colorings will end up like that.

Finally, you can do a BFS. For the search-border, you have a set of possibilities. Each element of the set, specifies for every vertex on the border, whether it needs another vertex of the same color or not. You want the keep the search border small.

It might be NPC. For that, consider the vertices on the search-border as propositional variables and prove that any propositional expression can expressed as such graph (I don't know if that is possible).

Lucas