# complete k-partite graph

A complete k-partite graph is a maximal k-partite graph. In other words, a graph is complete k-partite provided that its vertex set admits a partition $V=V_{1}\sqcup\dots\sqcup V_{k}$ such that for any $u\in V_{i}$ and $v\in V_{j}$, uv is an edge if and only if $i\neq j$.

For any tuple $(a_{1},\dots,a_{k})$, there is up to graph isomorphism a single complete k-partite graph with maximal stable sets $V_{1},\dots,V_{k}$ such that for each $i$, there are exactly $a_{i}$ vertices in $V_{i}$. This graph is denoted by $K_{a_{1},\dots,a_{k}}$.

Below we display the 3-partite complete graph $K_{2,3,4}$:

 $\xymatrix{&{\color[rgb]{1,0,0}A}\ar@{-}[dl]\ar@{-}[ddl]\ar@{-}[dddl]\ar@{-}[% ddddl]\ar@{-}[rrrdd]\ar@{-}[rrrddd]&{\color[rgb]{1,0,0}B}\ar@{-}[dll]\ar@{-}[% ddll]\ar@{-}[dddll]\ar@{-}[ddddll]\ar@{-}[rrdd]\ar@{-}[rrddd]&{\color[rgb]{% 1,0,0}C}\ar@{-}[dlll]\ar@{-}[ddlll]\ar@{-}[dddlll]\ar@{-}[ddddlll]\ar@{-}[rdd]% \ar@{-}[rddd]&\\ {\color[rgb]{0,0,1}D}\ar@{-}[rrrrd]\ar@{-}[rrrrdd]&&&&\\ {\color[rgb]{0,0,1}E}\ar@{-}[rrrr]\ar@{-}[rrrrd]&&&&{\color[rgb]{0,1,0}H}\\ {\color[rgb]{0,0,1}F}\ar@{-}[rrrru]\ar@{-}[rrrr]&&&&{\color[rgb]{0,1,0}I}\\ {\color[rgb]{0,0,1}G}\ar@{-}[rrrruu]\ar@{-}[rrrru]&&&&}$
Title complete k-partite graph CompleteKpartiteGraph 2013-03-22 12:17:18 2013-03-22 12:17:18 mps (409) mps (409) 8 mps (409) Definition msc 05C15 complete $k$-partite graph