Finding Δ(Σ) for a surface σ of characteristic χ(Σ) = −5 |
| |
| Authors: | Rong Luo Yue Zhao |
| |
| Institution: | 1. Department of Mathematical Sciences, Middle Tennessee State University, Murfreesboro, TN 37132;2. Department of Mathematics, University of Central Florida, Orlando, FL 32816‐1364 |
| |
| Abstract: | For each surface Σ, we define Δ(Σ) = max{Δ(G)|Gis a class two graph of maximum degree Δ(G) that can be embedded in Σ}. Hence, Vizing's Planar Graph Conjecture can be restated as Δ(Σ) = 5 if Σ is a plane. In this paper, we show that Δ(Σ) = 9 if Σ is a surface of characteristic χ(Σ) = ?5. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:148‐168, 2011 |
| |
| Keywords: | edge colorings class one class two critical graphs surfaces |
|
|
