THE COMPLEXITY OF HARMONIOUS COLORING FOR TREES

被引：37

作者：

EDWARDS, K ^{[1
]}

MCDIARMID, C ^{[1
]}

机构：

[1] UNIV OXFORD,DEPT STAT,OXFORD OX1 3TG,ENGLAND

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 57卷 / 2-3期

关键词：

D O I：

10.1016/0166-218X(94)00100-R

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring. It was shown by Hopcroft and Krishnamoorthy (1983) that the problem of determining the harmonious chromatic number of a graph is NP-hard. We show here that the problem remains hard even when restricted to trees.

引用

页码：133 / 144

页数：12