𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes

✍ Scribed by Ginn, Mark

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
88 KB
Volume
30
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the minimum set of unordered graphs that must be forbidden to get the same graph class characterized by forbidding a single ordered graph is infinite.

📜 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

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

Pancyclicity of 3-connected graphs: Pair
Pancyclicity of 3-connected graphs: Pairs of forbidden subgraphs
✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB

## Abstract We characterize all pairs of connected graphs {__X__, __Y__} such that each 3‐connected {__X__, __Y__}‐free graph is pancyclic. In particular, we show that if each of the graphs in such a pair {__X__, __Y__} has at least four vertices, then one of them is the claw __K__~1,3~, while the

Forbidden subgraphs and hamiitonian prop
Forbidden subgraphs and hamiitonian properties in the square of a connected graph
✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB 👁 1 views

Various Hamiltonian-like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K,+ the subdivision graph of &, and the subdivision graph of K1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the