Induced matchings in asteroidal triple-free graphs

✍ Scribed by Jou-Ming Chang

• Book ID: 104294290
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 193 KB
• Volume: 132
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00390-1

✦ Synopsis

An induced matching M of a graph G is a set of pairwise nonadjacent edges such that no two edges of M are joined by an edge in G. The problem of ÿnding a maximum induced matching is known to be NP-hard even for bipartite graphs of maximum degree four. In this paper, we study the maximum induced matching problem on classes of graphs related to AT-free graphs. We ÿrst deÿne a wider class of graphs called the line-asteroidal triple-free (LAT-free) graphs which contains AT-free graphs as a subclass. By examining the square of line graph of LAT-free graphs, we give a characterization of them and apply this for showing that the maximum induced matching problem and a generalization, called the maximum -separated matching problem, on LAT-free graphs can be solved in polynomial time. In fact, our result can be extended to the classes of graphs with bounded asteroidal index. Next, we propose a linear-time algorithm for ÿnding a maximum induced matching in a bipartite permutation (bipartite AT-free) graph using the greedy approach. Moreover, we show that using the same technique the minimum chain subgraph cover problem on bipartite permutation graphs can be solved with the same time complexity.