Atlas home || Conferences | Abstracts | about Atlas

21st Cumberland Conference on Graph Theory, Combinatorics, and Computing ---In Honor of Mike Plummer's 70th Birthday
May 15-17, 2008
Vanderbilt University
Nashville, TN, USA

Organizers
Mark Ellingham and Gexin Yu

View Abstracts
Conference Homepage

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.