On the strong chromatic index and maximum induced matching of tree-cographs and permutation graphs
Ton Kloks, Chin-Ting Ung, Yue-Li Wang · arXiv (Cornell University) · 2011
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 input. We also show that there exists an efficient algorithm for the strong chromatic index of permutation graphs.