graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a part of mathematics, a -partite graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be

colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow era to refer to an African American. In many places, it may be considered a slur. Dictionary definitions The word ''colored'' wa ...

with colors, so that no two endpoints of an edge have the same color. When these are the

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s, and when they are called the tripartite graphs. Bipartite graphs may be recognized in

polynomial time In theoretical 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 p ...

but, for any it is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, 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 In geometry, a regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex. Regular octahedra occur in nature as crystal structures. An octahedron, more generally, can be any eight-sided polyh ...

, 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 graph The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to di ...

s 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 graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...

s, the

cluster graph In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster g ...

s, are special cases of

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s, and can be recognized in polynomial time even when the partition is not supplied as part of the input.

References

{{reflist Graph families NP-complete problems