13
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ You will have to be more specific. It is not always possible to have a proper (vertex?) colouring of a graph of this sort: for instance, consider the 3-colouring of the 5-cycle. $\endgroup$
    – Niel de Beaudrap
    Commented Jul 8, 2010 at 9:08
  • 1
    $\begingroup$ Yes, I know, there may not be a proper vertex coloring (where each color is used at least twice) for a given graph. The question is that what is the complexity of checking this? $\endgroup$
    – Muse
    Commented Jul 8, 2010 at 9:25
  • $\begingroup$ Ah, sorry. Somehow I thought the question was how difficult it is to construct one (which obviously would help to answer your question). $\endgroup$
    – Niel de Beaudrap
    Commented Jul 8, 2010 at 11:42

6 Answers 6

Reset to default
8
$\begingroup$

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:

Hell, P.; Kirkpatrick, D. G., Packings by cliques and by finite families of graphs, Discrete Math. 49, 45–59 (1984). Zbl 0582.05046.

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

Cornuéjols, G.; Hartvigsen, D.; Pulleyblank, W., Packing subgraphs in a graph, Oper. Res. Lett. 1, 139–143 (1982). Zbl 0488.90070.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ +1 for the statement "it is not hard to show that it is in P. Or NP-complete..." $\endgroup$
    – Rune
    Commented Jul 8, 2010 at 22:28
  • $\begingroup$ If the graph has a perfect matching, then this suffices to yield a solution; but the original problem is not equivalent to whether the complement has a perfect matching. Again, consider the 5-cycle. --- More generally, it suffices for the complement to be covered by a vertex-disjoint collection of cliques, where each clique has size at least 2; a perfect matching is a special case. $\endgroup$
    – Niel de Beaudrap
    Commented Jul 9, 2010 at 13:08
  • 1
    $\begingroup$ That is why I wrote matching* and not matching - I said that we also allow K_3's to be matched together. It is unnecessary to allow bigger cliques. I don't get what you are trying to say with the 5-cycle. $\endgroup$
    – domotorp
    Commented Jul 9, 2010 at 13:37
  • $\begingroup$ A 5-cycle is it's own complement, and contains neither a perfect-matching, nor a perfect-matching-asterisk. Thus, the 5-cycle is a graph for which your reduction does not work. $\endgroup$
    – Niel de Beaudrap
    Commented Jul 12, 2010 at 13:01
  • $\begingroup$ I think that the 5-cycle is just a graph for which the answer is NO. As it contains no matching*, it does not have a coloring which each colorclass having size at least two. $\endgroup$
    – domotorp
    Commented Jul 12, 2010 at 19:51
3
$\begingroup$

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)

Improve this answer
$\endgroup$
4
  • $\begingroup$ @unknown: The paper is "Approximation algorithms and hardness results for the clique packing problem." Could you explain how the results in the paper address the posed question? The paper contains many results, and they are not phrased in the same terms as the posed problem. $\endgroup$
    – Joseph O'Rourke
    Commented Jul 9, 2010 at 10:11
  • $\begingroup$ see my answer for the connection $\endgroup$
    – domotorp
    Commented Jul 9, 2010 at 13:39
  • $\begingroup$ The coloring problem equivalent to partitioning the graph into cliques of size at least 2. This problem is quoted as polynomial-tim solvable in portal.acm.org/citation.cfm?id=1518279 . I refer to the 2nd paragraph in the introduction where it is stated that checking whether a graph can be packed by K_2, K_3,....K_n can be checked efficiently. 'Hell and Kirkpatrick [3] showed that this problem is NP-hard when F contains only complete graphs with at least three vertices, and it is polynomially solvable when F = {K2, . . . , Kr}, r > 2. $\endgroup$
    – Muse
    Commented Jul 9, 2010 at 14:07
  • $\begingroup$ @Muse & domotorp: Thanks for the clarifications! $\endgroup$
    – Joseph O'Rourke
    Commented Jul 9, 2010 at 14:35
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ nice observation...not sure what the complexity is if the degree is more than n/2. $\endgroup$
    – Muse
    Commented Jul 8, 2010 at 14:24
0
$\begingroup$

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

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ But there's no requirement for minimality here. $\endgroup$
    – rgrig
    Commented Jul 8, 2010 at 9:53
  • $\begingroup$ Yes, we don't need to use the minimum number of colors. So it does not follow from the first response that the problem is NP-hard $\endgroup$
    – Muse
    Commented Jul 8, 2010 at 10:12
  • $\begingroup$ Is it true that "if there is a good coloring then any minimum coloring is good"? (where 'good coloring' = 'proper vertex coloring with no solitary color' as required in the question) $\endgroup$
    – rgrig
    Commented Jul 8, 2010 at 14:13
  • $\begingroup$ It is not obvious...maybe it is true...not sure. $\endgroup$
    – Muse
    Commented Jul 8, 2010 at 14:23
  • 1
    $\begingroup$ No, it's false: consider a star plus an isolated vertex. There are two distinct minimal colorings; in one of them, the center vertex of the star is the only vertex of its color. $\endgroup$
    – JBL
    Commented Jul 8, 2010 at 15:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .