Multipartite graph: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 08:07, 16 July 2024

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]

Example complete $k$ -partite graphs
$K 2,2,2$	$K 3,3,3$	$K 2,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, $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 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.

References

^ Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, ISBN 0-7167-1045-5.
^ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111–114.
^ Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, CRC Press, p. 41, ISBN 9781584888017.

[1] Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4, ISBN 0-7167-1045-5.

[2] Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111–114.

[3] Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, CRC Press, p. 41, ISBN 9781584888017.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
+{{Short description|Graph able to be partitioned into multiple independent sets}}
-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 set (graph theory)|independent sets]]. Equivalently, it is a graph that can be [[graph coloring|colored]] with ''k'' colors, so that no two endpoints of an edge have the same color. When ''k''&nbsp;=&nbsp;2 these are the [[bipartite graph]]s, and when ''k''&nbsp;=&nbsp;3 they are called the '''tripartite graphs'''.
+In [[graph theory]], a part of mathematics, a '''{{mvar|k}}-partite graph''' is a [[Graph (discrete mathematics)|graph]] whose [[Vertex (graph theory)|vertices]] are (or can be) [[Graph partition|partitioned]] into {{mvar|k}} different [[independent set (graph theory)|independent sets]]. Equivalently, it is a graph that can be [[graph coloring|colored]] with {{mvar|k}} colors, so that no two endpoints of an edge have the same color. When {{math|1=''k'' = 2}} these are the [[bipartite graph]]s, and when {{math|1=''k'' = 3}} they are called the '''tripartite graphs'''.
-Bipartite graphs may be recognized in polynomial time but, for any ''k''&nbsp;>&nbsp;2
-it is [[NP-complete]], given an uncolored graph, to test whether it is ''k''-partite.<ref>{{citation
+Bipartite graphs may be recognized in [[polynomial time]] but, for any {{math|''k'' > 2}} it is [[NP-complete]], given an uncolored graph, to test whether it is {{mvar|k}}-partite.<ref>{{citation
- | last1 = Garey | first1 = M. R. | author1-link = Michael R. Garey
+ | last1 = Garey
- | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
- | at = GT4
+ | first1 = M. R.
+ | author1-link = Michael R. Garey
+ | last2 = Johnson
+ | first2 = D. S.
+ | author2-link = David S. Johnson
+ | at = [https://archive.org/details/computersintract0000gare/page/ GT4]
  | isbn = 0-7167-1045-5
  | publisher = W.H. Freeman
  | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
- | year = 1979}}.</ref>
+ | year = 1979
+ }}.</ref>
-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, [[folksonomy|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.<ref>{{citation
+However, in some applications of graph theory, a {{mvar|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, [[folksonomy|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.<ref>{{citation
  | last1 = Hotho | first1 = Andreas
  | last2 = Jäschke | first2 = Robert
@@ Line 21: / Line 27: @@
  | year = 2006}}.</ref>
 {| class=wikitable align=right width=320
-|+ Example complete ''k''-partite graphs
+|+ Example complete {{mvar|k}}-partite graphs
-!''K''<sub>2,2,2</sub>
+!{{math|''K''{{sub|2,2,2}}}}
-!''K''<sub>3,3,3</sub>
+!{{math|''K''{{sub|3,3,3}}}}
-!''K''<sub>2,2,2,2</sub>
+!{{math|''K''{{sub|2,2,2,2}}}}
 |- valign=top
 |[[File:Complex_tripartite_graph_octahedron.svg|100px]]<BR>Graph of [[octahedron]]
@@ Line 31: / Line 37: @@
 |}
-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, ''K''<sub>2,2,2</sub> 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''.<ref>{{citation
+A '''complete {{mvar|k}}-partite graph''' is a {{mvar|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 {{mvar|K}} subscripted by a sequence of the sizes of each set in the partition. For instance, {{math|''K''{{sub|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 {{mvar|k}}-partite for some {{mvar|k}}.<ref>{{citation
  | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
- | last2 = Zhang | first2 = Ping
+ | last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
  | isbn = 9781584888017
  | page = 41
@@ Line 41: / Line 47: @@
  | year = 2008}}.</ref>
 The [[Turán graph]]s 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 graph]]s, the [[cluster graph]]s, are special cases of [[cograph]]s, and can be recognized in polynomial time even when the partition is not supplied as part of the input.
+Complete {{mvar|k}}-partite graphs, complete multipartite graphs, and their [[complement graph]]s, the [[cluster graph]]s, are special cases of [[cograph]]s, and can be recognized in polynomial time even when the partition is not supplied as part of the input.
 ==References==
@@ Line 47: / Line 53: @@
 [[Category:Graph families]]
+[[Category:NP-complete problems]]