Induced matchings in intersection graphs Original Research Article

An induced matching in a graph G is a set of edges, no two of which meet a common node or are joined by an edge of G; that is, an induced matching is a matching which forms an induced subgraph. Induced matchings in graph G correspond precisely to independent sets of nodes in the square of the line-graph of G, which we denote by [L(G)]2. Often, if G has a nice representation as an intersection graph, we can obtain a nice representation of [L(G)]2 as an intersection graph. Then, if the independent set problem is polytime-solvable in [L(G)]2, the induced matching problem is polytime-solvable in G. In particular, we show that if G is a polygon-circle graph, then so is [L(G)]2, and the same holds for asteroidal triple-free and interval-filament graphs. It follows that the induced matching problem is polytime-solvable in these classes. Gavrilʹs interval-filament graphs include cocomparability and polygon-circle graphs, and the latter include circle graphs, circular-arc graphs, chordal graphs, and outerplanar graphs.