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