<p>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$).</p>

<p>Here is an interesting property: $G'$ is $\prod k_i$-colorable.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-11-22T16:27:37.037Z
2012-11-22T16:27:37.037Z
William Macrae
<p>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. 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 <strong>example</strong> below, what is the name of the resulting graph? </p>

CC BY-SA 3.0
2015-05-13T21:23:31.223Z
Your question is no longer self-contained since "example below" refers to nothing. Can you fix this?
Artem Kaznatcheev
<graph-theory>
Is there any special property the resulting graph G' has?
Micheal
# Is there any special property the resulting graph G' has?

(Asked by: username_0 on 2012-11-22)

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. 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?

**Tags:** graph-theory

> **Comments:**
> **username_1**: Your question is no longer self-contained since "example below" refers to nothing. Can you fix this?  

---

## 1 answers

### Answer by username_2 on 2012-11-22. Score: 8 | Accepted answer

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.


---

