A note on class one graphs with maximum degree six

摘要

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.