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.
| Original language | English |
|---|---|
| Pages (from-to) | 21-28 |
| Number of pages | 8 |
| Journal | Journal of Discrete Algorithms |
| Volume | 30 |
| DOIs | |
| Publication status | Published - 1 Jan 2015 |
| Externally published | Yes |
Keywords
- Chordal bipartite graph
- Induced matching
- Permutation graph
- Strong chromatic index
- Tree-cograph
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Access to Document
Other files and links
Fingerprint
Dive into the research topics of 'On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs'. Together they form a unique fingerprint.Cite this
Kloks, T., Poon, S. H., Ung, C. T., & Wang, Y. L. (2015). On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs. Journal of Discrete Algorithms, 30, 21-28. https://doi.org/10.1016/j.jda.2014.11.004