Document Open Access Logo

Clique-Width for Graph Classes Closed under Complementation

Authors Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, Viktor Zamaraev

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2017.73.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • clique-width
  • self-complementary graph
  • forbidden induced subgraph

Metrics

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

Abstract

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We initiate a systematic study into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded).
Once we have obtained the classification of the |H|=2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width  for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case  if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2).
Finally, we discuss the consequences of our results for COLOURING.

Cite As Get BibTex

Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev. Clique-Width for Graph Classes Closed under Complementation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.73

Author Details

Alexandre Blanché
Konrad K. Dabrowski
Matthew Johnson
Vadim V. Lozin
Daniël Paulusma
Viktor Zamaraev

References

  1. Lowell W. Beineke and Allen J. Schwenk. On a bipartite form of the Ramsey problem. Congressus Numerantium, XV:17-22, 1975. Google Scholar
  2. 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
  3. Rodica Boliac and Vadim V. Lozin. On the clique-width of graphs in hereditary classes. Proc. ISAAC 2002, LNCS, 2518:44-54, 2002. Google Scholar
  4. Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang, and Daniël Paulusma. Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211:30-39, 2016. Google Scholar
  5. Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang, and Daniël Paulusma. Bounding the clique-width of H-free chordal graphs. Journal of Graph Theory, (in press), 2017. Google Scholar
  6. Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, and Raffaele Mosca. New graph classes of bounded clique-width. Theory of Computing Systems, 38(5):623-645, 2005. Google Scholar
  7. Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, and Vadim V. Lozin. Clique-width for 4-vertex forbidden subgraphs. Theory of Computing Systems, 39(4):561-590, 2006. Google Scholar
  8. 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(1):173-188, 2006. Google Scholar
  9. Andreas Brandstädt, Hoàng-Oanh Le, and Raffaele Mosca. Gem- and co-gem-free graphs have bounded clique-width. International Journal of Foundations of Computer Science, 15(1):163-185, 2004. Google Scholar
  10. Andreas Brandstädt, Hoàng-Oanh Le, and Raffaele Mosca. Chordal co-gem-free and (P₅,gem)-free graphs have bounded clique-width. Discrete Applied Mathematics, 145(2):232-241, 2005. Google Scholar
  11. Andreas Brandstädt and Suhail Mahfud. Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Information Processing Letters, 84(5):251-259, 2002. Google Scholar
  12. Julia Chuzhoy. Improved bounds for the flat wall theorem. Proc. SODA 2015, pages 256-275, 2015. Google Scholar
  13. Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, and Udi Rotics. Polynomial-time recognition of clique-width ≤ 3 graphs. Discrete Applied Mathematics, 160(6):834-865, 2012. Google Scholar
  14. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. Google Scholar
  15. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1-3):77-114, 2000. Google Scholar
  16. Konrad K. Dabrowski, François Dross, and Daniël Paulusma. Colouring diamond-free graphs. Journal of Computer and System Sciences, (to appear). Google Scholar
  17. 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
  18. Konrad K. Dabrowski, Shenwei Huang, and Daniël Paulusma. Bounding clique-width via perfect graphs. Journal of Computer and System Sciences, (in press). Google Scholar
  19. Konrad K. Dabrowski, Vadim V. Lozin, and Daniël Paulusma. Clique-width and well-quasi ordering of triangle-free graph classes. Proc. WG 2017, LNCS, (to appear). Google Scholar
  20. Konrad K. Dabrowski, Vadim V. Lozin, and Daniël Paulusma. Well-quasi-ordering versus clique-width: New results on bigenic classes. Order, (to appear). Google Scholar
  21. Konrad K. Dabrowski, Vadim V. Lozin, Rajiv Raman, and Bernard Ries. Colouring vertices of triangle-free graphs without forests. Discrete Mathematics, 312(7):1372-1385, 2012. Google Scholar
  22. Konrad K. Dabrowski and Daniël Paulusma. Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200:43-51, 2016. Google Scholar
  23. Konrad K. Dabrowski and Daniël Paulusma. Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59(5):650-666, 2016. Google Scholar
  24. H. N. de Ridder et al. Information System on Graph Classes and their Inclusions, 2001-2013. http://www.graphclasses.org. Google Scholar
  25. 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
  26. Alastair Farrugia. Self-complementary graphs and generalisations: a comprehensive reference manual. Master’s thesis, University of Malta, 1999. Google Scholar
  27. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. Clique-width is NP-Complete. SIAM Journal on Discrete Mathematics, 23(2):909-939, 2009. Google Scholar
  28. Stéphane Földes and Peter Ladislaw Hammer. Split graphs. Congressus Numerantium, XIX:311-315, 1977. Google Scholar
  29. 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(4):331-363, 2017. Google Scholar
  30. Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded rank width. Proc. FOCS 2015, pages 1010-1029, 2015. Google Scholar
  31. Frank Gurski. The behavior of clique-width under graph operations and graph transformations. Theory of Computing Systems, 60(2):346-376, 2017. Google Scholar
  32. András Gyárfás. Problems from the world surrounding perfect graphs. Applicationes Mathematicae, 19(3-4):413-441, 1987. Google Scholar
  33. Öjvind Johansson. Clique-decomposition, NLC-decomposition, and modular decomposition - relationships and results for random graphs. Congressus Numerantium, 132:39-60, 1998. Google Scholar
  34. Marcin Kamiński, Vadim V. Lozin, and Martin Milanič. Recent developments on graphs of bounded clique-width. Discrete Applied Mathematics, 157(12):2747-2761, 2009. Google Scholar
  35. Daniel Kobler and Udi Rotics. Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics, 126(2-3):197-221, 2003. Google Scholar
  36. 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(1):195-206, 2004. Google Scholar
  37. Vadim V. Lozin and Dieter Rautenbach. The tree- and clique-width of bipartite graphs in special classes. Australasian Journal of Combinatorics, 34:57-67, 2006. Google Scholar
  38. Johann A. Makowsky and Udi Rotics. On the clique-width of graphs with few P₄’s. International Journal of Foundations of Computer Science, 10(03):329-348, 1999. Google Scholar
  39. Sang-Il Oum and Paul D. Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. Google Scholar
  40. Michaël Rao. MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoretical Computer Science, 377(1-3):260-267, 2007. Google Scholar
  41. Ronald C. Read. On the number of self-complementary graphs and digraphs. Journal of the London Mathematical Society, s1-38(1):99-104, 1963. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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