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

2011/10/08 by Ton Kloks, Kloks, Ton, Chin-Ting Ung +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DS

paper · pdf · doi:10.48550/arxiv.1110.1693

arxiv created 2011/10/08 · openalex publication_date 2011/10/08 · arxiv updated 2011/10/11 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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 exists an efficient algorithm for the strong chromatic index of permutation graphs.

Cited by

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

Related

• On the strong chromatic index and induced matching of tree-cographs, permutation graphs and chordal bipartite 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 edge coloring of Cayley graphs and some product graphs
• The Strong Chromatic Index of graphs with maximum degree Δ