Title

Finding The Exact Bound Of The Maximum Degrees Of Class Two Graphs Embeddable In A Surface Of Characteristic Ε{Lunate} ∈ {- 1, - 2, - 3}

Keywords

Class one; Class two; Critical graphs; Edge colorings; Surfaces

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 Σ, 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 ε{lunate} (Σ) = - 1 and Δ (Σ) = 8 if ε{lunate} (Σ) ∈ {- 2, - 3}. © 2007 Elsevier Inc. All rights reserved.

Publication Date

7-1-2008

Publication Title

Journal of Combinatorial Theory. Series B

Volume

98

Issue

4

Number of Pages

707-720

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.jctb.2007.11.002

Socpus ID

44249124581 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/44249124581

This document is currently not available here.

Share

COinS