|
Given a set F of graphs, a graph G is F-free if
G does not contain any member of F as an induced
subgraph. We say that F is a degree-sequence-forcing set if,
for each graph G in the class C of F-free
graphs, every realization of the degree sequence of G is also in
C. We prove that for any k there are finitely many minimal
degree-sequence-forcing sets with cardinality k. We also give a
complete characterization of the degree-sequence-forcing sets
F when F has cardinality at most two, and partial
results when F has cardinality three.
|