The Genus of the Complete Tripartite Graph (Solved)
Let K(a,b,c) denote the complete tripartite graph on partite sets of size a,b,c in descending order.
Problem: Find the orientable genus of K(a,b,c)
An obvious lower bound is given through Eulerís Formula and the fact that any embedding must have all faces at least a triangle. More subtly, the complete bipartite graph K(a,b+c) is a subgraph of K(a,b,c), and so the genus of the latter is at least the genus of the former. In his dissertation Art White conjectured that the genus always equals the larger of these two lower bounds. It is expected that this conjecture is difficult, since the borderline case involves embedding K(a,b+c) in a very special way.
The following cases are known:
2) a=mn, b=c=n
3) a=b=2n, c=n
4) a=b=2n, c=2n-2
5) b+c < 7.
David Craft showed the conjecture was true for
as well as various other cases.
SOLUTION: Mark Ellingham (personal communication) reports that a student of his has solved the problem completely. Moreover, it looks like their techniques may extend to the non-orientable case.
[C] D. Craft, Ph.D. dissertation,
Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,
Send comments to email@example.com
November 2002, modified December 2003