Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420914 | Discrete Applied Mathematics | 2007 | 6 Pages |
Abstract
In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Katerina Asdre, Kyriaki Ioannidou, Stavros D. Nikolopoulos,