On the strong chromatic index and induced matching of tree-cographs, permutation graphs and chordal bipartite graphs

Ton Kloks, Chin-Ting Ung, Yue-Li Wang

We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the…