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

Ton Kloks, Sheung Hung Poon, Chin Ting Ung, Yue Li Wang

Research output: Journal PublicationArticlepeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)21-28
Number of pages8
JournalJournal of Discrete Algorithms
Volume30
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes

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

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