k -partiter graph

from Wikipedia, the free encyclopedia
A 3-partiter graph. The light blue ovals are the 3 partition classes and

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 .


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


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:


With one notes a completely k -partite graph, with .

Example Turán graph

The Turán graph

The Turán graphs ( ) are full -partite graphs. The example opposite is 3-partit. Denotes the floor function , so is


This applies to the example opposite



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


Web links

Individual evidence

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