CS 789 THEORY SEMINAR [home]

Speaker:     Thanh Nguyen (http://www.cam.cornell.edu/~thanh/)
Title:           Subgraph characterization of Red/Blue-split graphs and König-Egerváry graphs

Date:           December 5, 2005  -- NOTE TIME  CHANGE: ***3:00pm***

Abstract:

König-Egerváry graphs (KEGs) are the graphs whose maximum size of a matching is equal to the minimum size of a vertex cover. We give an excluded subgraph characterization of KEGs by proving a more general result: excluded subgraph characterization of Red/Blue-split graphs.  We show several consequences of this result including theorems of Demming-Sterboul, Lovász, and Földes-Hammer.

Joint work with Ephraim Korach and Britta Peis to appear in SODA 2006.