On injective colourings of chordal graphs

被引：19

作者：

Hell, Pavol ^{[1
]}

Raspaud, Andre ^{[2
]}

Stacho, Juraj ^{[1
]}

机构：

[1] Simon Fraser Univ, Sch Comp Sci, 8888 Univ Dr, Burnaby, BC V5A 1S6, Canada

[2] Univ Bordeaux 1, Labri, F-33405 Bordeaux, France

来源：

LATIN 2008: THEORETICAL INFORMATICS | 2008年 / 4957卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1007/978-3-540-78773-0_45

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that one can compute the injective chromatic number of a chordal graph G at least as efficiently as one can compute the chromatic number of (G - B)(2), where B are the bridges of G. In particular, it follows that for strongly chordal graphs and so-called power chordal graphs the injective chromatic number can be determined in polynomial time. Moreover, for chordal graphs in general, we show that the decision problem with a fixed number of colours is solvable in polynomial time. On the other hand, we show that computing the injective chromatic number of a chordal graph is NP-hard; and unless NP = ZPP, it is hard to approximate within a factor of n(1/3-epsilon), for any epsilon > 0. For split graphs, this is best possible, since we show that the injective chromatic number of a split graph is (3)root n-approximable. (In the process, we correct a result of Agnarsson et al. on inapproximability of the chromatic number of the square of a split graph.)

引用

页码：520 / +

页数：2

共 20 条

[1]

[Anonymous], C NUMER

[2] Approximations for λ-colorings of graphs [J].