# 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 ${\ 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 \}}$