The Library
On injective colourings of chordal graphs
Tools
Hell, Pavol, Raspaud, André and Stacho, Juraj (2008) On injective colourings of chordal graphs. In: LATIN 2008: Theoretical Informatics, Búzios, Brazil, 7-11 Apr 2008. Published in: Lecture Notes in Computer Science, Vol.4957 pp. 520-530. doi:10.1007/978-3-540-78773-0_45 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-540-78773-0_45
Abstract
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 − ε , for any ε> 0. For split graphs, this is best possible, since we show that the injective chromatic number of a split graph is $\sqrt[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.)
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Book Title: | LATIN 2008: Theoretical Informatics | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.4957 | ||||
Page Range: | pp. 520-530 | ||||
DOI: | 10.1007/978-3-540-78773-0_45 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | LATIN 2008: Theoretical Informatics | ||||
Type of Event: | Conference | ||||
Location of Event: | Búzios, Brazil | ||||
Date(s) of Event: | 7-11 Apr 2008 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |