𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterizing path graphs by forbidden induced subgraphs

✍ Scribed by Benjamin Lévêque; Frédéric Maffray; Myriam Preissmann

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
197 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 Wiley Periodicals, Inc. J Graph Theory 62: 369–384, 2009

📜 SIMILAR VOLUMES

Characterizing directed path graphs by f
Characterizing directed path graphs by forbidden asteroids
✍ Kathie Cameron; Chính T. Hoàng; Benjamin Lévêque 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal grap

Line Graphs and Forbidden Induced Subgra
Line Graphs and Forbidden Induced Subgraphs
✍ Hong-Jian Lai; Ľubomı́r Šoltés 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 242 KB

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 con

Graph classes characterized both by forb
Graph classes characterized both by forbidden subgraphs and degree sequences
✍ Michael D. Barrus; Mohit Kumbhat; Stephen G. Hartke 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract Given a set ${\cal F}$ of graphs, a graph __G__ is ${\cal F}$‐free if __G__ does not contain any member of ${\cal F}$ as an induced subgraph. We say that ${\cal F}$ is a degree‐sequence‐forcing set if, for each graph __G__ in the class ${\cal C}$ of ${\cal F}$‐free graphs, every realiza

Forbidden induced subgraph characterizat
Forbidden induced subgraph characterization of cograph contractions
✍ Igor Ed. Zverovich; Inessa I. Zverovich 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

Let S 1 ; S 2 ; . . . ; S t be pairwise disjoint non-empty stable sets in a graph H. The graph H Ã is obtained from H by: (i) replacing each S i by a new vertex q i ; (ii) joining each q i and q j , 1 i 6 ¼ j t, and; (iii) joining q i to all vertices in HÀ(S 1 [ S 2 [ Á Á Á [ S t ) which were adjace

A semi-induced subgraph characterization
A semi-induced subgraph characterization of upper domination perfect graphs
✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl