Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

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 Σ, we define Δ ( Σ ) = max { Δ ( G ) | G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizingʹs Planar Graph Conjecture can be restated as Δ ( Σ ) = 5 if Σ is a plane. We show that Δ ( Σ ) = 7 if ϵ ( Σ ) = − 1 and Δ ( Σ ) = 8 if ϵ ( Σ ) ∈ { − 2 , − 3 } .