Counterexamples to the nonorientable genus conjecture for complete tripartite graphs

In 1976, Stahl and White conjectured that the minimum nonorientable genus of K-l,K-m,K-n (where l greater than or equal to m greater than or equal to n) is ... We prove that K-4,K-4,K-1 , K-4,K-4,K-3, and K-3 3,K-3 are counterexamples to this conjecture. We also show that all other complete tripartite graphs K-l,K-m,K-n with l greater than or equal to m greater than or equal to n and l less than or equal to 5 satisfy the conjecture. Moreover, all complete tripartite graphs with l less than or equal to 5 satisfy the similar conjecture for orientable genus. (C)0 2004 Elsevier Ltd. All rights reserved.