SIAM Journal on Discrete Mathematics · 2004 · 13 citations · 6 references
Natural SciencesMathematicsCombinatoricsComputational GeometryDiagrammingEnumerative CombinatoricsGraph Theory
In this paper, we obtain three general reduction formulas to determine the orientable and nonorientable genera for complete tripartite graphs. As corollaries, we (1) reduce the determination of the orientable (nonorientable, respectively) genera of 75 percent (85 percent, respectively) of nonsymmetric (with respect to l,m, and n) Kl,m,n to that of Km,m,n, and (2) determine the orientable and nonorientable genera for several classes of complete tripartite graphs.
6
The graph genus problem is NP-complete
Carsten Thomassen · Journal of Algorithms · 1989 · 259 citations
Blocks and the nonorientable genus of graphs
Saul Stahl, Lowell W. Beineke · Journal of Graph Theory · 1977 · 55 citations
The genus of the complete tripartite graph K
Arthur T. White · Journal of Combinatorial Theory · 1969 · 29 citations