k -partiter graph

A 3-partiter graph. The light blue ovals are the 3 partition classes and ${\displaystyle K_{1},K_{2}}$ ${\displaystyle K_{3}}$

In graph theory, a -partite graph is a simple graph whose node set breaks down into k disjoint subsets, so that the nodes of each of these subsets are not adjacent to one another. For these graphs are called bipartite graphs . ${\displaystyle k}$ ${\displaystyle k=2}$

Definitions

A k - partition of a graph is a partition of the vertex set into disjoint subsets , so that no adjazenten node in the same amount are, that is ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle V_{1},\ldots ,V_{k}}$ ${\displaystyle V_{i}}$

${\displaystyle \forall i\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{i}\rightarrow \{v,w\}\not \in E}$.

Note that such a k partition is not unique. It is entirely possible that there are multiple k partitions that satisfy this property. A graph is now called k - partite if he rejects a k has partition. The graph is called completely k-partit if, in addition, every node is connected to all nodes of all other k -partitions, so if:

${\displaystyle \forall i\neq j\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E}$.

With one notes a completely k -partite graph, with . ${\displaystyle K_{n_{1},\ldots ,n_{k}}}$ ${\displaystyle |V_{i}|=n_{i}}$

Example Turán graph

The Turán graph ${\displaystyle T_{3}(7)}$

The Turán graphs ( ) are full -partite graphs. The example opposite is 3-partit. Denotes the floor function , so is ${\displaystyle T_{m}(n)}$ ${\displaystyle 3\leq m<n}$ ${\displaystyle m}$ ${\displaystyle T_{3}(7)}$ ${\displaystyle \lfloor \cdot \rfloor }$

${\displaystyle T_{m}(n)=K_{\lfloor {\frac {n}{m}}\rfloor ,\lfloor {\frac {n+1}{m}}\rfloor ,\ldots ,\lfloor {\frac {n+m-1}{m}}\rfloor }}$.

This applies to the example opposite

${\displaystyle T_{3}(7)=K_{2,2,3}}$.

properties

• Every k-partite graph can be colored by k-nodes . Each partition class is assigned a color. The question of whether a graph is k-partit is equivalent to the question of whether the graph can be colored by k nodes. The chromatic number of a graph is therefore the smallest , so that a k has partition. ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$
• Every k -partite graph is also always a k + x -partite graph, where x is a natural number and k + x is smaller than the number of nodes .
• A completely k -partiter graph with always has a matching of the size , which can be calculated efficiently . ${\displaystyle K_{n_{1},\ldots ,n_{k}}}$ ${\displaystyle n_{1}\leq \ldots \leq n_{k}}$ ${\displaystyle \min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}}$

literature

• Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 ( diestel-graph-theory.com ).

Web links

• Eric W. Weisstein: k-Partite Graph . In: MathWorld (English).
• Eric W. Weisstein: Complete k-Partite Graph . In: MathWorld (English).
• Boris Bukh, Kevin Ferguson: k-partite graph . In: PlanetMath . (English)

Individual evidence

1. ↑ D. Sitton: Maximum Matchings in Complete Multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, pp. 6-16.