๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Characterization of Some Graph Classes with No Long Holes

โœ Scribed by E. Eschen; R. Sritharan

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
295 KB
Volume
65
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 that for triangulated graphs: (G) is a triangulated graph if and only if every induced subgraph (H) of (G) is either a clique or has two nonadjacent simplicial vertices of (H). 1995 Academic Press. Inc.

๐Ÿ“œ SIMILAR VOLUMES

A Characterization of Graphs with No Cub
A Characterization of Graphs with No Cube Minor
โœ John Maharry ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 418 KB

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-conn