𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Obstruction sets for outer-cylindrical graphs

✍ Scribed by Dan Archdeacon; C. Paul Bonnington; Nathaniel Dean; Nora Hartsfield; Katherine Scott

Publisher
John Wiley and Sons
Year
2001
Tongue
English
Weight
361 KB
Volume
38
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is outer‐cylindrical if it embeds in the sphere so that there are two distinct faces whose boundaries together contain all the vertices. The class of outer‐cylindrical graphs is closed under minors. We give the complete set of 38 minor‐minimal non‐outer‐cylindrical graphs, or equivalently, an excluded minor characterization of outer‐cylindrical graphs. We also give the obstruction sets under the related topological ordering and Y Δ‐ordering. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 42–64, 2001

📜 SIMILAR VOLUMES

On computing graph minor obstruction set
On computing graph minor obstruction sets
✍ Kevin Cattell; Michael J. Dinneen; Rodney G. Downey; Michael R. Fellows; Michael 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 149 KB

The Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many natural graph properties are characterized by a ÿnite set of forbidden substructures, the obstructions for the property. We prove several general theorems regarding the computation of obstruction sets from other

Ramsey numbers for sets of small graphs
Ramsey numbers for sets of small graphs
✍ Holger Brandes; Heiko Harborth; Hans-Dietrich O.F. Gronau; Christian Schwahn 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 733 KB

The Ramsey number r=r(G1-GZ-...-G,,,,H1-Hz-...-Hn) denotes the smallest r such that every 2-coloring of the edges of the complete graph K, contains a subgraph Gi with all edges of one color, or a subgraph Hi with all edges of a second color. These Ramsey numbers are determined for all sets of graph

Characterization problems for graphs, pa
Characterization problems for graphs, partially ordered sets, lattices, and families of sets
✍ William T. Trotter Jr.; John I. Moore Jr. 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 909 KB

A standard problem in combinatorial theory is to characterize structures which satisfy a certain property by providing a minimum list of forbidden substructures, for example, Kuratowski's well known characterization of planar graphs. In this paper, we establish connections between characterization p

Approximation Algorithms for Independent
Approximation Algorithms for Independent Sets in Map Graphs
✍ Zhi-Zhong Chen 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 172 KB

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + δ can be achieved by a quadratic-time algorithm for any given con

A rigid graph for every set
A rigid graph for every set
✍ Jaroslav Nešetřil 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 60 KB

## Abstract A graph __G__ is called __rigid__ if the identical mapping __V__(__G__)→__V__(__G__) is the only homomorphism __G__→__G__. In this note we give a simple construction of a rigid oriented graph on every set. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 108–110, 2002