Complete $k$-partite graphs that are $K_r$-free for some $k\in \mathbb{Z}^{+}$

75 Views Asked by At

I am aware that any complete $3$-partite graph is $K_r$ free for $r\ge 4$. However, I was curious whether there are any theorems on for which $k\in \mathbb{Z}^{+}$ and for which $r\in \mathbb{Z}^{+}$ a complete $k$-partite graph is $K_r$-free (i.e. does not have a $K_r$ as a subgraph).

It seems like at least $4$-partite graphs are certainly not $K_4$ free like $3$-partite graphs. This gave me the idea that $r-1$-partite graphs are $K_{r}$-free, since if we are looking for a $K_r$ in the $r-1$ partite graph, this would force us to place at least $2$ vertices in the same partite set. However, since the points in each partite set may not be connected with one another, we cannot create a complete graph $K_r$ as a subgraph of this $r-1$-partite graph.

Is this reasoning correct?

I would also want to be able to show that $r-1$-partite graphs must contain $K_{r-1}$ as a subgraph. It would seem to be sufficient to choose one vertex from each partite set, and this should form a $K_{r-1}$.

1

There are 1 best solutions below

0
On BEST ANSWER

Your reasoning is correct. Using the pigeonhole principle you have shown that the complete $m$-partite graph on $n$ vertices cannot contain an $m+1$-clique. Also, by selecting a single vertex from each partite set we can always create an $m$-clique, because each vertex is connected to all the vertices in the remaining partite sets.

In general, you may be interested in Turán graphs. They are exactly maximal - in the sense of the number of edges with a fixed number of vertices - $m$-partite graphs which are free of $m+1$ cliques.