Document Open Access Logo

Colouring Square-Free Graphs without Long Induced Paths

Authors Serge Gaspers, Shenwei Huang, Daniel Paulusma

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.35.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Serge Gaspers
Shenwei Huang
Daniel Paulusma

Cite AsGet BibTex

Serge Gaspers, Shenwei Huang, and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.STACS.2018.35

Abstract

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes characterized by one forbidden induced subgraph H. Despite a huge body of existing work, there are still major complexity gaps if two induced subgraphs H_1 and H_2 are forbidden. We let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t. We show that Colouring is polynomial-time solvable for s=4 and t<=6, which unifies several known results for Colouring on (H_1,H_2)-free graphs. Our algorithm is based on a novel decomposition theorem for (C_4,P_6)-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divide-and-conquer to bound the clique-width of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NP-complete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)-free graphs.
Keywords
  • graph colouring
  • hereditary graph class
  • clique-width
  • cycle
  • path

Metrics

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

References

  1. Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma. Hereditary graph classes: When the complexities of Colouring and Clique Cover coincide. CoRR, abs/1607.06757, 2016. Google Scholar
  2. John Adrian Bondy and Uppaluri S.R. Murty. Graph Theory, volume 244 of Springer Graduate Texts in Mathematics. Springer, 2008. Google Scholar
  3. Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica, (in press). Google Scholar
  4. Andreas Brandstädt and Chính T. Hoàng. On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theoretical Computer Science, 389:295-306, 2007. Google Scholar
  5. Andreas Brandstädt, Tilo Klembt, and Suhail Mahfud. P₆- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Mathematics and Theoretical Computer Science, 8:173-188, 2006. Google Scholar
  6. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: A Survey, volume 3 of SIAM Monographs on Discrete Mathematics and Applications. Philadelphia, 1999. Google Scholar
  7. Hajo Broersma, Petr A. Golovach, Daniël Paulusma, and Jian Song. Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time. Theoretical Computer Science, 423:1-10, 2012. Google Scholar
  8. Kathie Cameron and Chính T. Hoàng. Solving the clique cover problem on (bull,C₄)-free graphs. CoRR, abs/1704.00316, 2017. Google Scholar
  9. Maria Chudnovsky, Peter Maceli, Juraj Stacho, and Mingxian Zhong. 4-Coloring p₆-free graphs with no induced 5-cycles. Journal of Graph Theory, 84:262-285, 2017. Google Scholar
  10. Maria Chudnovsky and Juraj Stacho. 3-colorable subclasses of P₈-free graphs. Manuscript, 2017. Google Scholar
  11. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33:125-150, 2000. Google Scholar
  12. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101:77-114, 2000. Google Scholar
  13. Konrad K. Dabrowski, François Dross, and Daniël Paulusma. Colouring diamond-free graphs. Journal of Computer and System Sciences, 89:410-431, 2017. Google Scholar
  14. Konrad K. Dabrowski, Petr A. Golovach, and Daniël Paulusma. Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science, 522:34-43, 2014. Google Scholar
  15. Gabriel A. Dirac. On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25:71-76, 1961. Google Scholar
  16. 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
  17. Wolfgang Espelage, Frank Gurski, and Egon Wanke. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. Proc. WG 2001, LNCS, 2204:117-128, 2001. Google Scholar
  18. Serge Gaspers and Shenwei Huang. Linearly χ-bounding (P₆,C₄)-free graphs. Proc. WG 2017, LNCS, 10520:263-274, 2017. Google Scholar
  19. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. Journal of Graph Theory, 84:331-363, 2017. Google Scholar
  20. Petr A. Golovach and Daniël Paulusma. List coloring in the absence of two subgraphs. Discrete Applied Mathematics, 166:123-130, 2014. Google Scholar
  21. 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
  22. Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, volume 57 of Annals of Discrete Mathematics. North-Holland Publishing Co., 2004. Google Scholar
  23. Sylvain Gravier, Chính T. Hoàng, and Frédéric Maffray. Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Mathematics, 272:285-290, 2003. Google Scholar
  24. Martin Grötschel, László Lovász, and Alexander Schrijver. Polynomial algorithms for perfect graphs. Annals of Discrete Mathematics, 21:325-356, 1984. Google Scholar
  25. Pavol Hell and Shenwei Huang. Complexity of coloring graphs without paths and cycles. Discrete Applied Mathematics, 216, Part 1:211-232, 2017. Google Scholar
  26. Chính T. Hoàng, Marcin Kamiński, Vadim V. Lozin, Joe Sawada, and Xiao Shu. Deciding k-colorability of P₅-free graphs in polynomial time. Algorithmica, 57:74-81, 2010. Google Scholar
  27. Chính T. Hoàng and D. Adam Lazzarato. Polynomial-time algorithms for minimum weighted colorings of (P₅, ̅P₅)-free graphs and similar graph classes. Discrete Applied Mathematics, 186:106-111, 2015. Google Scholar
  28. Ian Holyer. The NP-Completeness of edge-coloring. SIAM Journal on Computing, 10:718-720, 1981. Google Scholar
  29. Shenwei Huang. Improved complexity results on k-coloring P_t-free graphs. European Journal of Combinatorics, 51:336-346, 2016. Google Scholar
  30. Shenwei Huang, Matthew Johnson, and Daniël Paulusma. Narrowing the complexity gap for colouring (C_s,P_t)-free graphs. The Computer Journal, 58:3074-3088, 2015. Google Scholar
  31. Tommy R. Jensen and Bjarne Toft. Graph Coloring Problems. Wiley Interscience, 1995. Google Scholar
  32. Marcin Kamiński, Vadim V. Lozin, and Martin Milanič. Recent developments on graphs of bounded clique-width. Discrete Applied Mathematics, 157:2747-2761, 2009. Google Scholar
  33. Thiyagarajan Karthick, Frédéric Maffray, and Lucas Pastor. Polynomial cases for the vertex coloring problem. CoRR, abs/1709.07712, 2017. Google Scholar
  34. Daniel Kobler and Udi Rotics. Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics, 126:197-221, 2003. Google Scholar
  35. 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
  36. Daniel Leven and Zvi Galil. NP completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4:35-44, 1983. Google Scholar
  37. László Lovász. Coverings and coloring of hypergraphs. Congressus Numerantium, VIII:3-12, 1973. Google Scholar
  38. Vadim V. Lozin and Dmitriy S. Malyshev. Vertex coloring of graphs with few obstructions. Discrete Applied Mathematics, 216, Part 1:273-280, 2017. Google Scholar
  39. Vadim V. Lozin and Dieter Rautenbach. On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM Journal on Discrete Mathematics, 18:195-206, 2004. Google Scholar
  40. Johann A. Makowsky and Udi Rotics. On the clique-width of graphs with few P₄’s. International Journal of Foundations of Computer Science, 10:329-348, 1999. Google Scholar
  41. Dmitriy S. Malyshev. The coloring problem for classes with two small obstructions. Optimization Letters, 8:2261-2270, 2014. Google Scholar
  42. Dmitriy S. Malyshev. Two cases of polynomial-time solvability for the coloring problem. Journal of Combinatorial Optimization, 31:833-845, 2016. Google Scholar
  43. Dmitriy S. Malyshev and O. O. Lobanova. Two complexity results for the vertex coloring problem. Discrete Applied Mathematics, 219:158-166, 2017. Google Scholar
  44. Michael Molloy and Bruce Reed. Graph Colouring and the Probabilistic Method. Springer-Verlag Berlin Heidelberg, 2002. Google Scholar
  45. Sang-Il Oum and Paul D. Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96:514-528, 2006. Google Scholar
  46. Michaël Rao. MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoretical Computer Science, 377:260-267, 2007. Google Scholar
  47. David Schindl. Some new hereditary classes where graph coloring remains NP-hard. Discrete Mathematics, 295:197-202, 2005. Google Scholar
  48. D. Seinsche. On a property of n-colorable graphs. Journal of Combinatorial Theory, Series B, 16:191-193, 1974. Google Scholar
  49. Robert E. Tarjan. Decomposition by clique separators. Discrete Mathematics, 55:221-232, 1985. 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 Imprint Privacy Contact