On injective colourings of chordal graphs

Abstract. We show that one can compute the injective chromatic num-ber 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 particu-lar, 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 n1/3−ǫ, for any ǫ> 0. For split graphs, this is best possible, since we show that the injective chromatic number of a split graph is 3 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.)