𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Line Graphs and Forbidden Induced Subgraphs

✍ Scribed by Hong-Jian Lai; Ľubomı́r Šoltés

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
242 KB
Volume
82
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Beineke and Robertson independently characterized line graphs in terms of nine forbidden induced subgraphs. In 1994, S8 olte s gave another characterization, which reduces the number of forbidden induced subgraphs to seven, with only five exceptional cases. A graph is said to be a dumbbell if it consists of two complete graphs sharing exactly one common edge. In this paper, we show that a graph with minimum degree at least seven that is not a dumbbell is a line graph if and only if it does not contain three forbidden induced subgraphs including K 1, 3 and K 5 &e. Applications of our main results to other forbidden induced subgraph characterizations of line graphs and to hamiltonian line graphs are also discussed.

2001 Academic Press

Throughout this paper, the notations G 1 , G 2 , ..., G 9 are exclusively used for these graphs shown in Fig. 1.

📜 SIMILAR VOLUMES

Characterizing path graphs by forbidden
Characterizing path graphs by forbidden induced subgraphs
✍ Benjamin Lévêque; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009

Hamiltonicity and forbidden subgraphs in
Hamiltonicity and forbidden subgraphs in 4-connected graphs
✍ Florian Pfender 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract Let __T__ be the line graph of the unique tree __F__ on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., __T__ is a chain of three triangles. We show that every 4‐connected {__T__, __K__~1,3~}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49:

On planar intersection graphs with forbi
On planar intersection graphs with forbidden subgraphs
✍ János Pach; Micha Sharir 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent

A result on Hamiltonian line graphs invo
A result on Hamiltonian line graphs involving restrictions on induced subgraphs
✍ H. J. Veldman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. O