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.
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets.
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
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]
Folksonomy is the system in which users apply public tags to online items, typically to make those items easier for themselves or others to find later. Over time, this can give rise to a classification system based on those tags and how often they are applied or searched for, in contrast to a taxonomic classification designed by the owners of the content and specified when it is published. This practice is also known as collaborative tagging, social classification, social indexing, and social tagging. Folksonomy was originally "the result of personal free tagging of information [...] for one's own retrieval", but online sharing and interaction expanded it into collaborative forms. Social tagging is the application of tags in an open online environment where the tags of other users are available to others. Collaborative tagging is tagging performed by a group of users. This type of folksonomy is commonly used in cooperative and collaborative projects such as research, content repositories, and social bookmarking.
| K2,2,2 | K3,3,3 | K2,2,2,2 |
|---|---|---|
 Graph of octahedron |  Graph of complex generalized octahedron |  Graph of 16-cell |
A complete k-partite graph is a k-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 K subscripted by a sequence of the sizes of each set in the partition. For instance, K2,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 the special case of complete multipartite graphs in which each two independent sets differ in size by at most one vertex. Complete k-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.
The Turán graphT(n,r) is a complete multipartite graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge if and only if they belong to different subsets. The graph will have subsets of size , and subsets of size . That is, it is a complete r-partite graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.
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 graphs are also called P3-free graphs. They are the complement graphs of the complete multipartite graphs and the 2-leaf powers.
