# Genus of the graph $K_{4,2,2,2}$

I have ask this question in math.stackexchange, here. Since, there is no answer and apart from that i feel that the problem is difficult, i would like to ask it here. The problem is to find the genus of $K_{4,2,2,2}$. I want a theoretical technique(if possible), otherwise using sage programming is good enough. I have tried using sage for a week now, but my computer is too slow. Thanks for any help.

The graph $K_{4,2,2,2}$ is a complete $4-$partite graph, that is, its vertex set can be partition into 4 disjoint parts of size 4, 2, 2 and 2, and any two vertices are adjacent if and only if they belong to different parts.

• – F. C. Mar 27 '14 at 8:14
• @F.C. But that question has no answer. If that question has an answer, then it will be an answer to this question also. – bor Mar 27 '14 at 8:34
• One lower bound is the genus of $K_{4,4,2}$, which is $2$. An upper bound is the genus of $K_{10}$, which is $4$. – Douglas Zare Mar 27 '14 at 9:14
• Since the answer is between $2$ and $4$, as shown by @DouglasZare, you might want to try the algebraic approach of Diestel and Bruhn (sciencedirect.com/science/article/pii/S0095895608000476). In fact, you might want to contact Henning Bruhn who might be able to compute this for you using their characterization! – Felix Goldberg Mar 27 '14 at 10:14
• If I'm not misreading, Theorem 4.1 from the reference given by David Wood states that the genus of the complete k-partite graph with partitions of sizes $V_1,V_2,\dots,V_k$ is $\sum_{i<j}\left\lceil\frac{(V_i-2)(V_j-2)}{4}\right\rceil+\left\lceil\frac{(k-3)(k-4)}{12}\right\rceil$, which gives zero for your graph. It also gives 1 for $K_{4,4,2}$ so I'm not sure what's going on. – j.c. Mar 27 '14 at 11:24

From the Euler equation, if $K_{4,2,2,2}$ has genus 2, it would actually triangulate $S_2$. Searching for triangular embeddings is much quicker than enumerating over all embeddings (as sage does). In fact, Jungerman was able to find a triangular embedding of $K_{18}-K_3$ in about half an hour back in the 1970s. Applying such an algorithm on $K_{4,2,2,2}$ shows that it has no such embedding on $S_2$.
Not only is $K_{4,2,2,2}$ a subgraph of $K_{10}$, as observed by @Douglas Zare, but it is a subgraph of $K_{10}-K_3$ as well, which has genus 3 (see Youngs, "The Heawood Map-Coloring Problem--Cases 1, 7, 10").
These two parts together show that the genus of $K_{4,2,2,2}$ is 3.