Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Undirected graph $G$ can be partitioned into several vertex blocks, each vertex pair $(u,v)$ has an edge if "$u$" and "$v$" are in the different blocks; no edge, otherwise. That is, each block pair induces a complete bipartite graph. Intuitively, if we use a vertex "$g$" to represent a block, and we add an edge $(g_i,g_j)$ if there are edges between the two blocks $i$ and $j$, then the graph $G$ is a clique.

Now, the question is: Suppose we have several such graphs $G_1,\ldots,G_n$, where a vertex $v_i$ may be in more than one $G_j$. If we combine graphs $G_1,\ldots,G_n$ by taking the union of their edge sets to get a graph $G'$, as shown in the example below, what is the name of the resulting graph? Does $G'$ have any special properties for the vertex cover problem or some other classical problems?

An example: example.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

The formal statement of the graph you are describing is the sum of $n$ complete $k_i$-partite graphs (where $k_i$ is the number of groups in $G_i$).

Here is an interesting property: $G'$ is $\prod k_i$-colorable.

A $k$-partite graph (assuming non-empty parts) is $k$-colorable (color all of the vertices in one part with the same color). A complete $k$-partite graph has chromatic number $k$ (clearly two vertices in two different parts require different colors). In fact, it has a maximal set of edges such that the graph has chromatic number $k$ (adding an edge within a part will force another color). If the graphs $G_1$ and $G_2$ are $k_1$ and $k_2$ colorable respectively, the sum $G = G_1 + G_2$ is $k_1k_2$ colorable by the product coloring. It follows that each $G_i$ is $k_i$ colorable, and that the sum, $G'$ is $\prod k_i$-colorable.

This property is tight if we know nothing more about the graphs. For arbitrary $n$ let $p_1p_2\cdots p_k$ be the prime factorization of $n$ (where repeated primes are listed repeatedly). If $G'$ is the sum of $k$ correctly-chosen complete $p_i$ partite graphs, $G' = K_n$. To choose $G_1$, let the parts be the residues modulo $p_1$. For $G_2$, let $i$ be in a part according to the residue of $\lfloor \frac{i}{p_1}\rfloor$ modulo $p_2$. Continuing this for each $k$ makes the right subgraphs. The best way to imagine this is to express $i$ has a number where the 1s place goes up to $p_1$, the $p_1$s place (the next digit over) goes up to $p_2$, etc. Then $G'$ is complete because if $i \neq j$ then The representations of $i$ and $j$ are different.

share|improve this answer
    
Thanks very much for your help! –  Miao Dongjing Feb 22 at 6:47

Your Answer

 
discard

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.