k -partiter graph
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 .
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
- .
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 graphs ( ) are full -partite graphs. The example opposite is 3-partit. Denotes the floor function , so is
- .
This applies to the example opposite
- .
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.
- 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 .
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
- ↑ D. Sitton: Maximum Matchings in Complete Multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, pp. 6-16.