Abstract
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring. The last problem is also known as L (1, 1)-Labelling and we also consider the framework of L (a , b)-Labelling. We prove a number of (almost-)complete complexity classifications, in particular, for Acyclic 3-Colouring, Star 3-Colouring and L (1, 2)-Labelling.
Daniël Paulusma—Supported by the Leverhulme Trust (RPG-2016-258).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albertson, M.O., Chappell, G.G., Kierstead, H.A., Kündgen, A., Ramamurthi, R.: Coloring with no 2-colored \({P}_4\)’s. Electron. J. Combinat. 11, R26 (2004)
Bodirsky, M., Kára, J., Martin, B.: The complexity of surjective homomorphism problems - a survey. Discrete Appl. Math. 160, 1680–1690 (2012)
Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: Approximations for lambda-colorings of graphs. Comput. J. 47, 193–204 (2004)
Bok, J., Jedlicková, N., Martin, B., Paulusma, D., Smith, S.: Acyclic, star and injective colouring: a complexity picture for \({H}\)-free graphs. In: Proceedings ESA 2020, LIPIcs 173, 22:1–22:22 (2020)
Bok, J., Jedličková, N., Martin, B., Paulusma, D., Smith, S.: Injective colouring for H-free graphs. In: Santhanam, R., Musatov, D. (eds.) CSR 2021. LNCS, vol. 12730, pp. 18–30. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79416-3_2
Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M., Paulusma, D.: Independent feedback vertex sets for graphs of bounded diameter. Inf. Process. Lett. 131, 26–32 (2018)
Brause, C., Golovach, P.A., Martin, B., Ochem, P., Paulusma D., Smith S.: Acyclic, star and injective colouring: bounding the diameter, Manuscript. arXiv:2104.10593 (2021)
Broersma, H., Fomin, F.V., Golovach, P.A., Paulusma, D.: Three complexity results on coloring \(P_k\)-free graphs. Eur. J. Combinat. 34(3), 609–619 (2013)
Calamoneri, T.: The \({L}(h, k)\)-labelling problem: an updated survey and annotated bibliography. Comput. J. 54, 1344–1371 (2011)
Edwards, K.: The complexity of colouring problems on dense graphs. TCS 43, 337–343 (1986)
Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5, 586–595 (1992)
Hahn, G., Kratochvíl, J., Širáň, J., Sotteau, D.: On the injective chromatic number of graphs. Discrete Math. 256, 179–192 (2002)
Hell, P., Raspaud, A., Stacho, J.: On injective colourings of chordal graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 520–530. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78773-0_45
Jin, J., Xu, B., Zhang, X.: On the complexity of injective colorings and its generalizations. Theoret. Comput. Sci. 491, 119–126 (2013)
Karthick, T.: Star coloring of certain graph classes. Graphs Combinat. 34, 109–128 (2018)
Martin, B., Paulusma, D., Smith, S.: Colouring graphs of bounded diameter in the absence of small cycles. In: Calamoneri, T., Corò, F. (eds.) CIAC 2021. LNCS, vol. 12701, pp. 367–380. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-75242-2_26
Martin, B., Paulusma, D., Smith, S.: Colouring \({H}\)-free graphs of bounded diameter. In: Proceedings MFCS 2019, LIPIcs 138, 14:1–14:14 (2019)
Mertzios, G.B., Spirakis, P.G.: Algorithms and almost tight results for 3-Colorability of small diameter graphs. Algorithmica 74, 385–414 (2016)
Paulusma, D.: Open problems on graph coloring for special graph classes. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 16–30. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53174-7_2
Shalu, M.A., Antony, C.: Complexity of restricted variant of star colouring. In: Changat, M., Das, S. (eds.) CALDAM 2020. LNCS, vol. 12016, pp. 3–14. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-39219-2_1
Yang, A., Yuan, J.: Partition the vertices of a graph into one independent set and one acyclic set. Discrete Math. 306, 1207–1216 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Brause, C., Golovach, P., Martin, B., Paulusma, D., Smith, S. (2021). Acyclic, Star, and Injective Colouring: Bounding the Diameter. In: Kowalik, Ł., Pilipczuk, M., Rzążewski, P. (eds) Graph-Theoretic Concepts in Computer Science. WG 2021. Lecture Notes in Computer Science(), vol 12911. Springer, Cham. https://doi.org/10.1007/978-3-030-86838-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-86838-3_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86837-6
Online ISBN: 978-3-030-86838-3
eBook Packages: Computer ScienceComputer Science (R0)