Graph classes characterized both by forbidden subgraphs and degree sequences
Michael D. Barrus, Mohit Kumbhat, Stephen G. Hartke · Journal of Graph Theory · 2007
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