NEW UPPER-BOUNDS ON HARMONIOUS COLORINGS

被引：22

作者：

EDWARDS, K ^{[1
]}

MCDIARMID, C ^{[1
]}

机构：

[1] UNIV OXFORD,DEPT STAT,OXFORD,ENGLAND

来源：

JOURNAL OF GRAPH THEORY | 1994年 / 18卷 / 03期

关键词：

D O I：

10.1002/jgt.3190180305

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We present an improved upper bound on the harmonious chromatic number of an arbitrary graph. We also consider ''fragmentable'' classes of graphs (an example is the class of planar graphs) that are, roughly speaking, graphs that can be decomposed. into bounded-sized components by removing a small proportion of the vertices. We show that for such graphs of bounded degree the harmonious chromatic number is close to the lower bound (2m)1/2, where m is the number of edges. (C) 1994 John Wiley & Sons, Inc.

引用

页码：257 / 267

页数：11

共 7 条

[1] A SEPARATOR THEOREM FOR GRAPHS OF BOUNDED GENUS [J].