Subgraph characterization of Red/Blue-split graphs and König-Egerváry graphs

Korach, Ephraim and Nguyen, Thành and Peis, Britta (2006) Subgraph characterization of Red/Blue-split graphs and König-Egerváry graphs.
Published In: SODA : Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Miami, FL., January 22 - 24, 2006 ACM 2006, pp. 842-850.

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. We show that KEGs are a special case of a more general class of graph: emph{Red/Blue-split} graphs, and give an excluded subgraph characterization of Red/Blue-split graphs. We show several consequences of this result including theorems of Deming-Sterboul, Lovász, and Földes-Hammer. A refined result of Schrijver on the integral solution of certain systems of linear inequalities is also given through the result on the weighted version of Red/Blue-split graphs.


Actions:
Download: [img] Postscript - Preprinted Version
Download (649Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (199Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-514
Depositing User: Britta Peis
Date Deposited: 09 May 2006 00:00
Last Modified: 12 Jan 2012 10:03
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/514