Prospective Students Current Students Business & Industry Faculty & Staff Alumni Visitors
 
[an error occurred while processing this directive]
[an error occurred while processing this directive]
Stephen Hartke
University of Illinois, Urbana-Champaign

Graph classes characterized both by forbidden subgraphs and degree sequences

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.


Thursday, October 26, E1 Room TBA, 4pm

Last updated by Robert Ellis on 08/29/06

© 2008 Illinois Institute of Technology 3300 South Federal Street, Chicago, IL 60616-3793 Tel 312.567.3000
[an error occurred while processing this directive]