Document Open Access Logo

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs

Authors Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, Erik Jan van Leeuwen

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.83.pdf
  • Filesize: 494 kB
  • 13 pages

Document Identifiers

Author Details

Pinar Heggernes
  • Department of Informatics, University of Bergen, Norway
Davis Issac
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Germany
Juho Lauri
  • Nokia Bell Labs, Dublin, Ireland
Paloma T. Lima
  • Department of Informatics, University of Bergen, Norway
Erik Jan van Leeuwen
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands

Cite As Get BibTex

Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, and Erik Jan van Leeuwen. Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.83

Abstract

Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question.
We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Rainbow coloring
  • graph classes
  • polynomial-time algorithms
  • approximation algorithms

Metrics

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

References

  1. Akanksha Agrawal. Fine-grained complexity of rainbow coloring and its variants. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 60:1-60:14, 2017. Google Scholar
  2. Prabhanjan Ananth, Meghana Nasre, and Kanthi K. Sarpatwar. Rainbow connectivity: Hardness and tractability. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 241-251, 2011. Google Scholar
  3. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: A Survey. SIAM Monographs in Discrete Mathematics and Applications, 1999. Google Scholar
  4. Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster. Hardness and algorithms for rainbow connection. Journal of Combinatorial Optimization, 21(3):330-347, 2011. Google Scholar
  5. L. Sunil Chandran and Deepak Rajendraprasad. Rainbow Colouring of Split and Threshold Graphs. In Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON), volume 7434 of Lecture Notes in Computer Science, pages 181-192. Springer, 2012. Google Scholar
  6. L. Sunil Chandran and Deepak Rajendraprasad. Inapproximability of rainbow colouring. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 153-162, 2013. Google Scholar
  7. L. Sunil Chandran, Deepak Rajendraprasad, and Marek Tesař. Rainbow colouring of split graphs. Discrete Applied Mathematics, 216:98-113, 2017. Google Scholar
  8. Gary Chartrand, Garry L Johns, Kathleen A McKeon, and Ping Zhang. Rainbow connection in graphs. Mathematica Bohemica, 133(1):85-98, 2008. Google Scholar
  9. Lily Chen, Xueliang Li, and Huishu Lian. Further hardness results on the rainbow vertex-connection number of graphs. Theoretical Computer Science, 481:18-23, 2013. Google Scholar
  10. Lily Chen, Xueliang Li, and Yongtang Shi. The complexity of determining the rainbow vertex-connection of a graph. Theoretical Computer Science, 412(35):4531-4535, 2011. Google Scholar
  11. Paul Dorbec, Ingo Schiermeyer, Elżbieta Sidorowicz, and Éric Sopena. Rainbow connection in oriented graphs. Discrete Applied Mathematics, 179:69-78, 2014. Google Scholar
  12. Eduard Eiben, Robert Ganian, and Juho Lauri. On the complexity of rainbow coloring problems. In Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA), volume 9538 of Lecture Notes in Computer Science, pages 209-220. Springer, 2015. Google Scholar
  13. Eduard Eiben, Robert Ganian, and Juho Lauri. On the complexity of rainbow coloring problems. Discrete Applied Mathematics, 246:38-48, 2018. Google Scholar
  14. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some Simplified NP-Complete Graph Problems. Theoretical Compututer Science, 1(3):237-267, 1976. Google Scholar
  15. Pavol Hell and Jing Huang. Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs. SIAM Journal on Discrete Mathematics, 18(3):554-570, 2004. Google Scholar
  16. Melissa Keranen and Juho Lauri. Computing minimum rainbow and strong rainbow colorings of block graphs. arXiv preprint arXiv:1405.6893, 2014. Google Scholar
  17. Łukasz Kowalik, Juho Lauri, and Arkadiusz Socała. On the fine-grained complexity of rainbow coloring. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA), pages 58:1-58:16, 2016. Google Scholar
  18. Michael Krivelevich and Raphael Yuster. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3):185-191, 2010. Google Scholar
  19. Juho Lauri. Chasing the Rainbow Connection: Hardness, Algorithms, and Bounds. PhD thesis, Tampere University of Technology, 2016. Google Scholar
  20. Juho Lauri. Further hardness results on rainbow and strong rainbow connectivity. Discrete Applied Mathematics, 201:191-200, 2016. Google Scholar
  21. Juho Lauri. Complexity of rainbow vertex connectivity problems for restricted graph classes. Discrete Applied Mathematics, 219:132-146, 2017. Google Scholar
  22. Van Bang Le and Zsolt Tuza. Finding optimal rainbow connection is hard. Technical Report CS-03-09, Universität Rostock, 2009. Google Scholar
  23. Shasha Li, Xueliang Li, and Yongtang Shi. Note on the complexity of deciding the rainbow (vertex-)connectedness for bipartite graphs. Applied Mathematics and Computation, 258:155-161, 2015. Google Scholar
  24. Xueliang Li, Yaping Mao, and Yongtang Shi. The strong rainbow vertex-connection of graphs. Utilitas Mathematica, 93:213-223, 2014. Google Scholar
  25. Xueliang Li, Yongtang Shi, and Yuefang Sun. Rainbow connections of graphs: A survey. Graphs and Combinatorics, 29(1):1-38, 2013. Google Scholar
  26. László Lovász. Coverings and colorings of hypergraphs. In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 3-12, 1973. Google Scholar
  27. Jeremy Spinrad, Andreas Brandstädt, and Lorna Stewart. Bipartite permutation graphs. Discrete Applied Mathematics, 18(3):279-292, 1987. Google Scholar
  28. Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, and Xiao Zhou. On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms. Algorithmica, 67(2):161-179, 2013. Google Scholar
  29. Ryuhei Uehara and Gabriel Valiente. Linear structure of bipartite permutation graphs and the longest path problem. Information Processing Letters, 103(2):71-77, 2007. Google Scholar
  30. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 681-690. ACM, 2006. 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