A note on class one graphs with maximum degree six |
| |
Authors: | Xuechao Li Jianbing Niu |
| |
Institution: | a Division of Academic Enhancement, The University of Georgia, Athens, GA 30602, USA b Department of Mathematical Sciences, Middle Tennessee State University, Murfreesboro, TN 37132, USA c Department of Mathematics, West Virginia University, Morgantown, WV 26505, USA |
| |
Abstract: | It is known that there are class two graphs with Δ=6 which can be embedded in a surface Σ with Euler characteristic χ(Σ)?0. However, it is unknown whether there are class two graphs on the projective plane or on the plane with Δ=6. In this paper, we prove that every graph with Δ=6 is class one if it can be embedded in a surface with Euler characteristic at least -3 and is C3-free, or C4-free or if it can be embedded in a surface with Euler characteristic at least -1 and is C5-free. This generalizes Zhou's results in G. Zhou, A note on graphs of class I, Discrete Math. 263 (2003) 339-345] on planar graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|