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

doi:10.1016/j.jda.2014.11.004

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 Publication › Article › peer-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 language	English
Pages (from-to)	21-28
Number of pages	8
Journal	Journal of Discrete Algorithms
Volume	30
DOIs	https://doi.org/10.1016/j.jda.2014.11.004
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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.jda.2014.11.004

Cite this

@article{5aed61029cfb43409d1fa8489eae7eef,

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

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.",

keywords = "Chordal bipartite graph, Induced matching, Permutation graph, Strong chromatic index, Tree-cograph",

author = "Ton Kloks and Poon, {Sheung Hung} and Ung, {Chin Ting} and Wang, {Yue Li}",

year = "2015",

month = jan,

day = "1",

doi = "10.1016/j.jda.2014.11.004",

language = "English",

volume = "30",

pages = "21--28",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Kloks, Ton

AU - Poon, Sheung Hung

AU - Ung, Chin Ting

AU - Wang, Yue Li

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

KW - Chordal bipartite graph

KW - Induced matching

KW - Permutation graph

KW - Strong chromatic index

KW - Tree-cograph

UR - http://www.scopus.com/inward/record.url?scp=84922465763&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2014.11.004

DO - 10.1016/j.jda.2014.11.004

M3 - Article

AN - SCOPUS:84922465763

SN - 1570-8667

VL - 30

SP - 21

EP - 28

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this