NONORIENTABLE TRIANGULAR EMBEDDINGS OF COMPLETE GRAPHS WITH ARBITRARILY LARGE LOOSENESS

Abstract

The looseness of a triangular embedding of a complete graph in a closed surface is the minimum integer m such that for every assignment of m colors to the vertices of the embedding (such that all m colors are used) there is a face incident with vertices of three distinct colors. In this paper we show that for every p >= 3 there is a nonorientable triangular embedding of a complete graph with looseness at least p. (C) 2007 Elsevier B.V. All rights reserved.