Multipartite graph

In the mathematical field of graph theory, a tripartite graph is a graph whose vertices are partitioned into three sets (called partitions) in such a way that no two vertices contained in any one of the three parts are adjacent.^[1]

General definition of k-partite graphs

A graph G is k-partite with vertex classes V₁, V₂, V₃, …,V_k if V(G) = V₁ ∪ V₂ ∪ V₃ ∪ …∪ V_k and V_i ∩ V_j = ∅ whenever 1 ≤ i < j ≤ k and no edge joins two vertices in the same class.^[2] This means that the vertices of the graph can be partitioned in k independent sets, which are sometimes called the partite sets of the partition.^[3]

Tripartite graphs

The tripartite graphs are the special case of k-partite graphs when k is equal to 3. This means that we can divide the vertices (nodes) of the graph in three independent sets (let's call them M, N, and R) in such a way that every vertex in set M is connected only to vertices belonging to sets N and R, every vertex in set N is connected only to vertices belonging to sets M and R and every vertex in set R is connected only to vertices belonging to M and N.

The three sets M, N, and R may be thought of as a coloring of the graph with three colors: if one colors all nodes in M blue, all nodes in N red and all nodes in R yellow, each edge will have endpoints of differing colors.

Complete tripartite graphs

A complete tripartite graph G, using the notation K_(m,n,r), has the following properties:^[4]

The vertices can be partitioned into 3 subsets: M, N, and R.
Each vertex in M is connected to all vertices in N and R.

Each vertex in N is connected to all vertices in in M and R.

Each vertex in R is connected to all vertices in M and N.

No vertex in M is connected to any other vertices in M.

No vertex in N is connected to any other vertices in N.

No vertex in R is connected to any other vertices in R.

References

^ http://www.edmath.org/MATtours/discrete/concepts/cbipar.html
^ Bollobás, B., Modern Graph Theory, 1998, Springer Science+Business Media, USA, page 6
^ Gross, J.L.; Yellen, J., Graph Theory and its applications, Second edition, 2006, Chapman and Hall, Boca Raton, USA, page 378
^ http://faculty.kutztown.edu/rieksts/225/graphs/tripartite.html

[1] ttp://www.edmath.org/MATtours/discrete/concepts/cbipar.html

[2] Bollobás, B., Modern Graph Theory, 1998, Springer Science+Business Media, USA, page 6

[3] Gross, J.L.; Yellen, J., Graph Theory and its applications, Second edition, 2006, Chapman and Hall, Boca Raton, USA, page 378

[4] ttp://faculty.kutztown.edu/rieksts/225/graphs/tripartite.html

[1]

[2]

[3]

[4]