✦ LIBER ✦

A Characterization of Graphs with No Cube Minor

✍ Scribed by John Maharry

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 418 KB
Volume: 80
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1968

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V n for some n 6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles.

📜 SIMILAR VOLUMES

A Splitter for Graphs with No Petersen F

A Splitter for Graphs with No Petersen Family Minor

✍ John Maharry 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 231 KB

The Petersen family consists of the seven graphs that can be obtained from the Petersen Graph by Y2-and 2Y-exchanges. A splitter for a family of graphs is a maximal 3-connected graph in the family. In this paper, a previously studied graph, Q 13, 3 , is shown to be a splitter for the set of all grap

Projective-Planar Graphs with No K3, 4-M

Projective-Planar Graphs with No K3, 4-Minor

✍ John Maharry; Daniel Slilaty 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB

Defective choosability of graphs with no

Defective choosability of graphs with no edge-plus-independent-set minor

✍ Douglas R. Woodall 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB

## Abstract It is proved that, if __s__ ≥ 2, a graph that does not have __K__~2~ + __K__~__s__~ = __K__~1~ + __K__~1, __s__~ as a minor is (__s__, 1)\*‐choosable. This completes the proof that such a graph is (__s__ + 1 − __d__,__d__)\*‐choosable whenever 0 ≤ __d__ ≤ __s__ −1 © 2003 Wiley Periodica

A Characterization of Some Graph Classes

A Characterization of Some Graph Classes with No Long Holes

✍ E. Eschen; R. Sritharan 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 295 KB

We give a characterization of a hierarchy of graph classes with no long holes in which each class excludes some long antiholes. At one end of the hierarchy is the class of graphs with no long holes. At the other end is the class of weakly triangulated graphs. The characterization has the flavor of t

A characterization of Seymour graphs

✍ Ageev, A. A.; Kostochka, A. V.; Szigeti, Z. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

A connected undirected graph G is called a Seymour graph if the maximum number of edge disjoint T -cuts is equal to the cardinality of a minimum T -join for every even subset T of V (G). Several families of graphs have been shown to be subfamilies of Seymour graphs (Seymour

A characterization of ptolemaic graphs

✍ Edward Howorka 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 466 KB

A connected graph G is ptolernaic provided that for each four vertices u,, 1 5 i 5 4, of G, the six distances d, =dG (u,ui), i f j satisfy the inequality d,2d34 5 d,3d24 + d,4d23 (shown by Ptolemy t o hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showe