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.)
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agnarsson, G., Greenlaw, R., Halldorsson, M.: On Powers of Chordal Graphs and Their Colorings. Congress Numerantium 100, 41–65 (2000)
Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: Approximations for λ-Coloring of Graphs. The Computer Journal 47, 193–204 (2004)
Calamoneri, T.: The L(h,k)-Labelling Problem: A Survey and Annotated Bibliography. The Computer Journal 49, 585–608 (2006)
Diestel, R.: Graph Theory, 3rd edn. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2005)
Ekim, T., Hell, P., Stacho, J., de Werra, D.: Polarity of Chordal Graphs. Discrete Applied Mathematics (to appear)
Farber, M.: Characterizations of strongly chordal graphs. Discrete Mathematics 43, 173–189 (1983)
Feder, T., Hell, P., Klein, S., Nogueira, L.T., Protti, F.: List matrix partitions of chordal graphs. Theoretical Computer Science 349, 52–66 (2005)
Feige, U., Killian, J.: Zero Knowledge and the Chromatic Number. Journal of Computer and System Sciences 57, 187–199 (1998)
Fiala, J., Kratochvíl, J.: Partial covers of graphs. Discussiones Mathematicae Graph Theory 22, 89–99 (2002)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics 5, 586–595 (1992)
Hahn, G., Kratochvíl, J., Širáň, J., Sotteau, D.: On the injective chromatic number of graphs. Discrete Mathematics 256, 179–192 (2002)
Hell, P., Klein, S., Nogueira, L.T., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics 141, 185–194 (2004)
Jensen, T.R., Toft, B.: Graph coloring problems. Wiley Interscience Series in Discrete Mathematics. Wiley, New York (1995)
Kráľ, D.: Coloring Powers of Chordal Graphs. SIAM Journal on Discrete Mathematics 18, 451–461 (2005)
Laskar, R., Shier, D.: On powers and centers of chordal graphs. Discrete Applied Mathematics 6, 139–147 (1983)
Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC), pp. 571–575.
J. Stacho: Ph.D. Thesis, Simon Fraser University (2008)
Tarjan, R.: Decomposition by clique separators. Discrete Mathematics 55, 221–232 (1985)
West, D.: Introduction to Graph Theory. Prentice Hall, Englewood Cliffs (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hell, P., Raspaud, A., Stacho, J. (2008). On Injective Colourings of Chordal Graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_45
Download citation
DOI: https://doi.org/10.1007/978-3-540-78773-0_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78772-3
Online ISBN: 978-3-540-78773-0
eBook Packages: Computer ScienceComputer Science (R0)