Achromatic number is NP-complete for cographs and interval graphs
type: Item
instance of: scholarly article
title: Achromatic number is NP-complete for cographs and interval graphs
zbMATH Open document ID: 0684.68046
DOI: 10.1016/0020-0190(89)90221-4
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://dspace.library.uu.nl/handle/1874/16576
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4121423
zbMATH Keywords: cographs
zbMATH Keywords: interval graphs
zbMATH Keywords: NP-complete
author: Hans L. Bodlaender
MaRDI profile type: Publication
OpenAlex ID: W2160875590
Wikidata QID: Q56390758
cites work: Q3812222
cites work: Total domination in interval graphs
cites work: Complement reducible graphs
cites work: Q4198056
cites work: The edge inducibility of graphs
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: The NP-completeness column: an ongoing guide
cites work: Finding Hamiltonian circuits in interval graphs
cites work: Finding the minimum bandwidth of an interval graph
cites work: Q3686754
DBLP publication ID: journals/ipl/Bodlaender89
Recommended article: Algorithms - ESA 2003
Recommended article: Q3126442
Recommended article: Q3320413
Recommended article: Concerning the achromatic number of graphs
Recommended article: Q3216676
Recommended article: On the edge achromatic numbers of complete graphs
Recommended article: Q4970154
Recommended article: Achromatic numbers for circulant graphs and digraphs
Recommended article: Q3325761
Recommended article: Q4498314
description: scientific article; zbMATH DE number 4121423