𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterizing directed path graphs by forbidden asteroids

✍ Scribed by Kathie Cameron; Chính T. Hoàng; Benjamin Lévêque

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
135 KB
Volume
68
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non-adjacent vertices are linked by a special connection if either they Contract grant sponsor: Natural Sciences and Engineering Research Council of Canada (NSERC).

📜 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

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