Why does $K_{\chi(H)}(|H|)$ contain the graph H?

49 Views Asked by At

Why does $K_{\chi(H)}(|H|)$ necessarily contain the graph H? This is part of the more general question as to why $K_{\chi(H)}(t)$ should contain H for sufficiently large t. Here $K_{r}(t)$ is a complete r-partite graph with t vertices in each vertex class.

1

There are 1 best solutions below

2
On BEST ANSWER

How to find a copy of $H$ in $K_{\chi(H)}(|H|)$:

Label each of the vertex classes of $K_{\chi(H)}(|H|)$ as $V_{1},...,V_{\chi(H)}$. Start by coloring the vertices of $H$ with $\chi(H)$ colors (proper coloring), i.e. colors $\{1, 2, 3, ..., \chi(H)\}$. Map each color to a vertex class, and map each vertex that is colored with that color to a distinct vertex in the class. I.e. every vertex that is colored $i$ gets mapped to a distinct vertex in $V_{i}$. This can be done since $H$ can be colored with $\chi(H)$ colors and no more that $|H|$ vertices get mapped to any one class $V_{i}$. Now, the vertices that you've mapped to form a complete $\chi(H)$-partite graph. So every edge possible is there (except edges between vertices of the same color), but you know in $H$ vertices of the same color did not have an edge between them to begin with.