The b-chromatic number of a graph

被引：160

作者：

Irving, RW ^{[1
]}

Manlove, DF ^{[1
]}

机构：

[1] Univ Glasgow, Dept Comp Sci, Glasgow G12 8QQ, Lanark, Scotland

来源：

DISCRETE APPLIED MATHEMATICS | 1999年 / 91卷 / 1-3期

基金：

英国工程与自然科学研究理事会;

关键词：

complexity; graph; colouring; achromatic; b-chromatic;

D O I：

10.1016/S0166-218X(98)00146-2

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The achromatic number psi(G) of a graph G=(V,E) is the maximum k such that V has a partition V-1, V-2,...,V-k into independent sets, the union of no pair of which is independent. Were we show that psi(G) can be viewed as the maximum over all minimal elements of a partial order defined on the set of all colourings of G. We introduce a natural refinement of this partial order, giving rise to a new parameter, which we call the b-chromatic number, phi(G), of G. We prove that determining phi(G) is NP-hard for general graphs, but polynomial-time solvable for trees. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：127 / 141

页数：15