The harmonious coloring problem is NP-complete for interval and permutation graphs
type: Item
instance of: scholarly article
title: The harmonious coloring problem is NP-complete for interval and permutation graphs
zbMATH Open document ID: 1125.05036
author: Katerina Asdre
author: Kyriaki Ioannidou
author: Stavros D. Nikolopoulos
published in: Discrete Applied Mathematics
publication date: 2007-10-29T00:00:00Z
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5206110
zbMATH Keywords: harmonious coloring
zbMATH Keywords: harmonious chromatic number
zbMATH Keywords: achromatic number
zbMATH Keywords: interval graphs
zbMATH Keywords: permutation graphs
zbMATH Keywords: NP-completeness
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2007.07.005
OpenAlex ID: W2015078128
cites work: Linear algorithm for optimal path cover problem on interval graphs
cites work: NP-completeness results for some problems on subclasses of bipartite and chordal graphs
cites work: Total domination in interval graphs
cites work: Achromatic number is NP-complete for cographs and interval graphs
cites work: Graph Classes: A Survey
cites work: Q4364806
cites work: Complement reducible graphs
cites work: Q4352945
cites work: `` Strong '' NP-Completeness Results
cites work: Q4198056
cites work: Q3328583
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: The achromatic number of a graph
cites work: Q5578801
cites work: Finding Hamiltonian circuits in interval graphs
cites work: An optimal path cover algorithm for cographs
cites work: Edge Dominating Sets in Graphs
DOI: 10.1016/J.DAM.2007.07.005
description: scientific article; zbMATH DE number 5206110