2- and 3-factors of graphs on surfaces
It has been conjectured that any 5-connected graph embedded in a surface ? with sufficiently large face-width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4-connected graphs. In this article, we shall study the existence of 2- and 3-factors in a graph embedded in a surface ?. A hamiltonian cycle is a special case of a 2-factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2-factor. In fact, we only need the 4-connectivity with minimum degree at least 5. In addition, our face-width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface ? of Euler genus g.
factors hamiltonian cycle graphs on a surface