Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic is an element of is an element of{-1,-2,-3}

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Sigma, we define Delta(Sigma) = max{Delta(G)vertical bar G is a class two graph of maximum degree Delta that can be embedded in Sigma}. Hence Vizing\u27s Planar Graph Conjecture can be restated as Delta(Sigma) = 5 if Sigma is a plane. We show that Delta(Sigma) = 7 if is an element of(Z) = -1 and Delta(Sigma) = 8 if is an element of(Sigma) is an element of {-2, -3). (c) 2007 Elsevier Inc. All rights reserved