Relation between a complete k-partite graph and a perfect graph

165 Views Asked by At

Is a complete $k$-partite graph also a perfect graph?

I know that the result holds for bipartite graphs. Can we claim the same for higher order partitions?

1

There are 1 best solutions below

0
On

Any complete $k$-partite graph $K_{a_1,a_2,\ldots,a_k}$ has chromatic number $k$ (it has a $k$-clique and is $k$-colorable by coloring the parts distinct colors).

Any induced subgraph of $K_{a_1,a_2,\ldots,a_k}$ has the form $K_{b_1,b_2,\ldots,b_l}$, which has chromatic number $l$ (by the above), which is the size of the largest clique.

So, yes, they are perfect.