Title

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

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