**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:

*1)
**a=b=c*

*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

*1)
**b=c*

*2)
**b=2c*

*3)
**b=c+1*

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.**

**References:**

[C] D. Craft, Ph.D. dissertation,

Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,

Send comments to *dan.archdeacon@uvm.edu*

November 2002, modified December 2003