Document Open Access Logo

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

Authors Jan Bok , Nikola Jedlic̆ková , Barnaby Martin, Daniël Paulusma , Siani Smith

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.22.pdf
  • Filesize: 0.78 MB
  • 22 pages

Document Identifiers

Author Details

Jan Bok
  • Computer Science Institute, Charles University, Prague, Czech Republic
Nikola Jedlic̆ková
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic
Barnaby Martin
  • Department of Computer Science, Durham University, UK
Daniël Paulusma
  • Department of Computer Science, Durham University, UK
Siani Smith
  • Department of Computer Science, Durham University, UK

Funding

  • Bok, Jan: Supported by GAUK 1580119 and SVV - 2020 - 260578.
  • Jedlic̆ková, Nikola: Supported by GAUK 1198419 and SVV - 2020 - 260578.
  • Paulusma, Daniël: Supported by the Leverhulme Trust (RPG-2016-258).

Cite As Get BibTex

Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Daniël Paulusma, and Siani Smith. Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.22

Abstract

A k-colouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. 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. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as L(1,1)-Labelling).
A classical complexity result on Colouring is a well-known dichotomy for H-free graphs, which was established twenty years ago (in this context, a graph is H-free if and only if it does not contain H as an induced subgraph). Moreover, this result has led to a large collection of results, which helped us to better understand the complexity of Colouring. In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. 
We initiate such a systematic complexity study, and similar to the study of Colouring we use the class of H-free graphs as a testbed. We prove the following results:  
1) We give almost complete classifications for the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring for H-free graphs. 
2) If the number of colours k is fixed, that is, not part of the input, we give full complexity classifications for each of the three problems for H-free graphs.  From our study we conclude that for fixed k the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • acyclic colouring
  • star colouring
  • injective colouring
  • H-free
  • dichotomy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Michael O. Albertson, Glenn G. Chappell, Henry A. Kierstead, André Kündgen, and Radhika Ramamurthi. Coloring with no 2-colored P₄’s. Electronic Journal of Combinatorics, 11, 2004. Google Scholar
  2. Noga Alon, Colin McDiarmid, and Bruce A. Reed. Acyclic coloring of graphs. Random Structures and Algorithms, 2:277-288, 1991. Google Scholar
  3. Noga Alon and Ayal Zaks. Algorithmic aspects of acyclic edge colorings. Algorithmica, 32:611-614, 2002. Google Scholar
  4. Patrizio Angelini and Fabrizio Frati. Acyclically 3-colorable planar graphs. Journal of Combinatorial Optimization, 24:116-130, 2012. Google Scholar
  5. Aistis Atminas, Vadim V. Lozin, and Igor Razgon. Linear time algorithm for computing a small biclique in graphs without long induced paths. Proceedings of SWAT 2012, LNCS, 7357:142-152, 2012. Google Scholar
  6. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305-1317, 1996. Google Scholar
  7. Hans L. Bodlaender, Ton Kloks, Richard B. Tan, and Jan van Leeuwen. Approximations for lambda-colorings of graphs. Computer Journal, 47:193-204, 2004. Google Scholar
  8. Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent feedback vertex set for P₅-free graphs. Algorithmica, 81:1342-1369, 2019. Google Scholar
  9. Oleg V. Borodin. On acyclic colorings of planar graphs. Discrete Mathematics, 25:211-236, 1979. Google Scholar
  10. Hajo Broersma, Petr A. Golovach, Daniël Paulusma, and Jian Song. Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science, 414:9-19, 2012. Google Scholar
  11. Tiziana Calamoneri. The L(h,k)-labelling problem: An updated survey and annotated bibliography. Computer Journal, 54:1344-1371, 2011. Google Scholar
  12. Christine T. Cheng, Eric McDermid, and Ichiro Suzuki. Planarization and acyclic colorings of subcubic claw-free graphs. Proc. of WG 2011, LNCS, 6986:107-118, 2011. Google Scholar
  13. Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, and Mingxian Zhong. List-three-coloring graphs with no induced P₆+rP₃. CoRR, abs/1806.11196, 2018. URL: http://arxiv.org/abs/1806.11196.
  14. Thomas F. Coleman and Jin-Yi Cai. The cyclic coloring problem and estimation of sparse Hessian matrices. SIAM Journal on Algebraic Discrete Methods, 7:221-235, 1986. Google Scholar
  15. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85:12-75, 1990. Google Scholar
  16. Zdeněk Dvořák, Bojan Mohar, and Robert Šámal. Star chromatic index. Journal of Graph Theory, 72(3):313-326, 2013. Google Scholar
  17. Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter. Uniquely colourable graphs and the hardness of colouring graphs of large girth. Combinatorics, Probability and Computing, 7:375-386, 1998. Google Scholar
  18. Paul Erdős. Graph theory and probability. Canadian Journal of Mathematics, 11:34-38, 1959. Google Scholar
  19. Guillaume Fertin, Emmanuel Godard, and André Raspaud. Minimum feedback vertex set and acyclic coloring. Information Processing Letters, 84:131-139, 2002. Google Scholar
  20. Guillaume Fertin and André Raspaud. Acyclic coloring of graphs of maximum degree five: Nine colors are enough. Information Processing Letters, 105:65-72, 2008. Google Scholar
  21. Guillaume Fertin, André Raspaud, and Bruce A. Reed. Star coloring of graphs. Journal of Graph Theory, 47(3):163-182, 2004. Google Scholar
  22. Jiří Fiala, Petr A. Golovach, and Jan Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theoretical Computer Science, 412:2513-2523, 2011. Google Scholar
  23. Jiří Fiala, Petr A. Golovach, Jan Kratochvíl, Bernard Lidický, and Daniël Paulusma. Distance three labelings of trees. Discrete Applied Mathematics, 160:764-779, 2012. Google Scholar
  24. Jiří Fiala, Ton Kloks, and Jan Kratochvíl. Fixed-parameter complexity of lambda-labelings. Discrete Applied Mathematics, 113:59-72, 2001. Google Scholar
  25. Esther Galby, Paloma T. Lima, Daniël Paulusma, and Bernard Ries. Classifying k-edge colouring for H-free graphs. Information Processing Letters, 146:39-43, 2019. Google Scholar
  26. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990. Google Scholar
  27. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of colouring graphs with forbidden subgraphs. Journal of Graph Theory, 84:331-363, 2017. Google Scholar
  28. Petr A. Golovach, Daniël Paulusma, and Jian Song. Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics, 167:107-120, 2014. Google Scholar
  29. Geňa Hahn, Jan Kratochvíl, Jozef Širáň, and Dominique Sotteau. On the injective chromatic number of graphs. Discrete Mathematics, 256:179-192, 2002. Google Scholar
  30. Pavol Hell, André Raspaud, and Juraj Stacho. On injective colourings of chordal graphs. Proc. LATIN 2008, LNCS, 4957:520-530, 2008. Google Scholar
  31. Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10:718-720, 1981. Google Scholar
  32. Shenwei Huang, Matthew Johnson, and Daniël Paulusma. Narrowing the complexity gap for colouring (C_s,P_t)-free graphs. Computer Journal, 58:3074-3088, 2015. Google Scholar
  33. Jing Jin, Baogang Xu, and Xiaoyan Zhang. On the complexity of injective colorings and its generalizations. Theoretical Computer Science, 491:119-126, 2013. Google Scholar
  34. Ross J. Kang and Tobias Müller. Frugal, acyclic and star colourings of graphs. Discret. Appl. Math., 159:1806-1814, 2011. Google Scholar
  35. T. Karthick. Star coloring of certain graph classes. Graphs and Combinatorics, 34:109-128, 2018. Google Scholar
  36. Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-free graphs. Proc. ISAAC 2018, LIPIcs, 123:5:1-5:13, 2018. Google Scholar
  37. Daniel Král', Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs. Proc. WG 2001, LNCS, 2204:254-262, 2001. Google Scholar
  38. Hui Lei, Yongtang Shi, and Zi-Xia Song. Star chromatic index of subcubic multigraphs. Journal of Graph Theory, 88:566-576, 2018. Google Scholar
  39. Daniel Leven and Zvi Galil. NP-completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4:35-44, 1983. Google Scholar
  40. Cláudia Linhares-Sales, Ana Karolinna Maia, Nícolas A. Martins, and Rudini Menezes Sampaio. Restricted coloring problems on graphs with few P₄’s. Annals of Operations Research, 217:385-397, 2014. Google Scholar
  41. Errol L. Lloyd and Subramanian Ramanathan. On the complexity of distance-2 coloring. Proc. ICCI 1992, pages 71-74, 1992. Google Scholar
  42. Vadim V. Lozin and Marcin Kamiński. Coloring edges and vertices of graphs without short or long cycles. Contributions to Discrete Mathematics, 2(1), 2007. Google Scholar
  43. Andrew Lyons. Acyclic and star colorings of cographs. Discrete Applied Mathematics, 159:1842-1850, 2011. Google Scholar
  44. Mohammad Mahdian. On the computational complexity of strong edge coloring. Discrete Applied Mathematics, 118:239-248, 2002. Google Scholar
  45. Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman, and Sue Whitesides. Acyclic coloring with few division vertices. Journal of Discrete Algorithms, 23:42-53, 2013. Google Scholar
  46. Stephan Olariu. Paw-free graphs. Information Processing Letters, 28:53-54, 1988. Google Scholar
  47. Neil Robertson, Daniel P. Sanders, Paul D. Seymour, and Robin Thomas. The four-colour theorem. Journal of Combinatorial Theory, Series B, 70:2-44, 1997. Google Scholar
  48. Arunabha Sen and Mark L. Huson. A new model for scheduling packet radio networks. Wireless Networks, 3:71-82, 1997. Google Scholar
  49. Vadim Georgievich Vizing. On an estimate of the chromatic class of a p-graph. Diskret Analiz, 3:25-30, 1964. Google Scholar
  50. David R. Wood. Acyclic, star and oriented colourings of graph subdivisions. Discrete Mathematics and Theoretical Computer Science, 7:37-50, 2005. Google Scholar
  51. Xiao-Dong Zhang and Stanislaw Bylka. Disjoint triangles of a cubic line graph. Graphs and Combinatorics, 20:275-280, 2004. Google Scholar
  52. Xiao Zhou, Yasuaki Kanari, and Takao Nishizeki. Generalized vertex-coloring of partial k-trees. IEICE Transactions on Fundamentals of Electronics, Communication and Computer Sciences, E83-A:671-678, 2000. Google Scholar
  53. Enqiang Zhu, Zepeng Li, Zehui Shao, and Jin Xu. Acyclically 4-colorable triangulations. Information Processing Letters, 116:401-408, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact