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

2011/10/17 by Ton Kloks, Kloks, Ton, Chin-Ting Ung +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1110.3583

arXiv admin note: substantial text overlap with arXiv:1110.1693

arxiv created 2013/07/31 · arxiv updated 2013/08/01

Abstract

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 exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.

Citations

• On the strong chromatic index and maximum induced matching of tree-cographs and permutation graphs

Related

• On the strong chromatic index and maximum induced matching of tree-cographs and permutation graphs
• Algorithms for the strong chromatic index of Halin graphs, distance-hereditary graphs and maximal outerplanar graphs
• A linear-time algorithm for the strong chromatic index of Halin graphs
• Strong chromatic index of chordless graphs
• Strong chromatic index of bipartite graphs