Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic |
| |
| Authors: | Rong Luo Yue Zhao |
| |
| Institution: | aDepartment of Mathematical Sciences, Middle Tennessee State University, Murfreesboro, TN 37130, USA;bDepartment of Mathematics, University of Central Florida, Orlando, FL 32816-1364, USA |
| |
| 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  (Σ)=−1 and Δ(Σ)=8 if (Σ) {−2,−3}. |
| |
| Keywords: | Edge colorings Class one Class two Critical graphs Surfaces |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
