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}

    Authors

    R. Luo;Y. Zhao

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Comb. Theory Ser. B

    Keywords

    edge colorings; class one; class two; critical graphs; surfaces; INDEX-CRITICAL GRAPHS; EDGE COLORINGS; MAP; Mathematics

    Abstract

    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's 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.

    Journal Title

    Journal of Combinatorial Theory Series B

    Volume

    98

    Issue/Number

    4

    Publication Date

    1-1-2008

    Document Type

    Article

    Language

    English

    First Page

    707

    Last Page

    720

    WOS Identifier

    WOS:000256598500006

    ISSN

    0095-8956

    Share

    COinS