Graph classes characterized both by forbidden subgraphs and degree sequences

Time

-

Locations

E1 106





Description

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.

Tags: