Multipartite graph

In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are or can be partitioned into k different independent sets. Equivalently, it is a graph that can be colored with k colors, so that no two endpoints of an edge have the same color. When k = 2 these are the bipartite graphs, and when k = 3 they are called the tripartite graphs.

Bipartite graphs may be recognized in polynomial time but, for any k > 2 it is NP-complete, given an uncolored graph, to test whether it is k-partite.^[1] However, in some applications of graph theory, a k-partite graph may be given as input to a computation with its coloring already determined; this can happen when the sets of vertices in the graph represent different types of objects. For instance, folksonomies have been modeled mathematically by tripartite graphs in which the three sets of vertices in the graph represent users of a system, resources that the users are tagging, and tags that the users have applied to the resources.^[2]

The complete tripartite graph K_2,2,2, the graph of the octahedron

A complete k-partite graph is a graph that can be partitioned into k independent sets, as above, so that every pair of vertices from two different independent sets have different colors. These graphs are described by notation with a capital letter K subscripted by a sequence of the sizes of each set in the partition. For instance, K_2,2,2 is the complete tripartite graph of a regular octahedron, which can be partitioned into three independent sets each consisting of two opposite vertices. A complete multipartite graph is a graph that is complete k-partite for some k.^[3] The Turán graphs are a special case of the complete multipartite graphs in which each two partition sets differ in size by at most one vertex. Complete k-partite graphs and complete multipartite graphs are a special case of the cographs, and can be recognized in polynomial time even when the partition is not supplied as part of the input.

References