✦ LIBER ✦

2- and 3-factors of graphs on surfaces

✍ Scribed by Ken-Ichi Kawarabayashi; Kenta Ozeki

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 94 KB
Volume: 67
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20533

No coin nor oath required. For personal study only.

✦ Synopsis

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.

(1) If G is 4-connected and minimum degree of G is at least 5, and furthermore, face-width of G is at least 4g -12, then G has a 2-factor. (2) If G is 5-connected and face-width of G is at least max{44g -117, 5}, then G has a 3-factor.

📜 SIMILAR VOLUMES

2-connected 7-coverings of 3-connected g

2-connected 7-coverings of 3-connected graphs on surfaces

✍ Ken-ichi Kawarabayashi; Atsuhiro Nakamoto; Katsuhiro Ota 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract An __m__‐__covering__ of a graph __G__ is a spanning subgraph of __G__ with maximum degree at most __m__. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus __k__ ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most

Decomposition of Graphs on Surfaces

✍ Maurits de Graaf; Alexander Schrijver 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 266 KB

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let G=(V, E) be an Eulerian graph embedded on a triangulizable surface S. We show that E can be decomposed into closed curves C 1 , ..., C k such that mincr(G, D)= k i=1 mincr(C i , D) for each closed curve D on S. Here min

On 2-factors of a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2-factor with exactly k components? We will prove that if , then, for any bipartite graph H = (U 1 , U 2 ; F ) with |U 1 | ≤ n, |U 2 | ≤ n and ∆(H) ≤ 2, G contains a subgraph i

3-Coloring graphs embedded in surfaces

✍ Zhao, Yue 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 3 views

In this article, we show that there exists an integer k(Σ)

Coloring Face-Hypergraphs of Graphs on S

Coloring Face-Hypergraphs of Graphs on Surfaces

✍ André Kündgen; Radhika Ramamurthi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 223 KB

The face-hypergraph, H(G), of a graph G embedded in a surface has vertex set V(G), and every face of G corresponds to an edge of H(G) consisting of the vertices incident to the face. We study coloring parameters of these embedded hypergraphs. A hypergraph is k-colorable (k-choosable) if there is a c

The Spectral Radius of Graphs on Surface

The Spectral Radius of Graphs on Surfaces

✍ M.N. Ellingham; Xiaoya Zha 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 152 KB

This paper provides new upper bounds on the spectral radius \ (largest eigenvalue of the adjacency matrix) of graphs embeddable on a given compact surface. Our method is to bound the maximum rowsum in a polynomial of the adjacency matrix, using simple consequences of Euler's formula. Let # denote th