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