|
Organizers |
Minimum chain subgraph covers and maximum induced matchings in chordal bipartite graphs
by
R. Sritharan
University of Dayton
Coauthors: Atif Abueida (University of Dayton),
Arthur H. Busch (University of Dayton)
A chain graph is a bipartite graph with no induced 2K2. We show that when G = (V, E) is a bipartite graph with no induced cycles on six vertices, the minimum number of chain subgraphs of G needed to cover E(G) equals the chromatic number of the complement of the square of line graph of G. Using this, we show that when G = (V, E) is chordal bipartite, the minimum number of chain subgraphs of G needed to cover E(G) equals the size of a largest induced matching in G, and that such a cover and matching can be found in polynomial time. We also present more efficient algorithms for a subclass of chordal bipartite graphs.
Date received: April 12, 2008
Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-35.