✦ LIBER ✦

Supereulerian graphs and excluded induced minors

✍ Scribed by Hong-Jian Lai

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 494 KB
Volume: 146
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00159-7

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if a graph G with r'(G) 1> 2 does not have an induced subgraph contractible to K2, 3 or to one of the subdivided wheels, then G has a spanning eulerian subgraph. As a corollary, such a graph has a nowhere-zero 4-flow.

📜 SIMILAR VOLUMES

Supereulerian complementary graphs

✍ Hong-Jian Lai 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 541 KB

## Abstract Nebeský in [12] show that for any simple graph with __n__ ≥ 5 vertices, either __G__ or __G^c^__ contains an eulerian subgraph with order at least __n__ ‐ 1, with an explicitly described class of exceptional graphs. In this note, we show that if __G__ is a simple graph with __n__ ≥ 61 v

Supereulerian Graphs and the Petersen Gr

Supereulerian Graphs and the Petersen Graph

✍ Paul A. Catlin; Hong-Jian Lai 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 619 KB

Any 3-edge-connected graph with at most 10 edge cuts of size 3 either has a spanning closed trail or it is contractible to the Petersen graph.

Supereulerian graphs: A survey

✍ Paul A. Catlin 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 996 KB

## Abstract A graph is __supereulerian__ if it has a spanning eulerian subgraph. There is a rduction method to determine whether a graph is supereulerian, and it can also be applied to study other concepts, e.g., hamiltonian line graphs, a certain type of double cycle cover, and the total interval

A reduction criterion for supereulerian

A reduction criterion for supereulerian graphs

✍ Catlin, Paul A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

Let G be a graph, and let H be a connected subgraph of G. When it is known that the graph G/H (obtained from G by contracting H to a vertex) has a spanning eulerian subgraph, under what conditions can it be inferred that G itself has a spanning eulerian subgraph? 0 1996 John Wiley & Sons, Inc.

Excluding Induced Subdivisions of the Bu

Excluding Induced Subdivisions of the Bull and Related Graphs

✍ Maria Chudnovsky; Irena Penev; Alex Scott; Nicolas Trotignon 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract For any graph __H__, let Forb\*(__H__) be the class of graphs with no induced subdivision of __H__. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph __H__, there is a function __f__~__H__~: ℕ→ℝ such that for every graph __G__∈Forb\*(__H__), χ(__G__)≤__f__

Complete minors in pseudorandom graphs

✍ Andrew Thomason 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 1 views