✦ LIBER ✦
Graph classes characterized both by forbidden subgraphs and degree sequences
✍ Scribed by Michael D. Barrus; Mohit Kumbhat; Stephen G. Hartke
- Publisher
- John Wiley and Sons
- Year
- 2007
- Tongue
- English
- Weight
- 198 KB
- Volume
- 57
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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 realization of the degree sequence of G is also in ${\cal C}$. We give a complete characterization of the degree‐sequence‐forcing sets ${\cal F}$ when ${\cal F}$ has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131–148, 2008