In
graph theory, a part of mathematics, a -partite graph is a
graph whose
vertices are (or can be)
partitioned into different
independent sets. Equivalently, it is a graph that can be
colored with colors, so that no two endpoints of an edge have the same color. When these are the
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
s, and when they are called the tripartite graphs.
Bipartite graphs may be recognized in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
but, for any it is
NP-complete, given an uncolored graph, to test whether it is -partite.
However, in some applications of graph theory, a -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.
A complete -partite graph is a -partite graph in which there is an edge between every pair of vertices from different independent sets. These graphs are described by notation with a capital letter subscripted by a sequence of the sizes of each set in the partition. For instance, 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 -partite for some .
[.]
The
Turán graphs are the special case of complete multipartite graphs in which each two independent sets differ in size by at most one vertex.
Complete -partite graphs, complete multipartite graphs, and their
complement graphs, the
cluster graphs, are special cases of
cographs, and can be recognized in polynomial time even when the partition is not supplied as part of the input.
References
{{reflist
Graph families