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?
1
-
$\begingroup$ Your question is no longer self-contained since "example below" refers to nothing. Can you fix this? $\endgroup$ – Artem Kaznatcheev♦ May 13 '15 at 21:23
Add a comment
|
$\begingroup$
$\endgroup$
0
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.
