Skip to main content
Top

2015 | OriginalPaper | Chapter

Bounding the Clique-Width of H-free Chordal Graphs

Authors : Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed that the gem and the co-gem are the only two 1-vertex \(P_4\)-extensions H for which the class of H-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we prove that the clique-width is:
(i)
bounded for four classes of H-free chordal graphs;
 
(ii)
unbounded for three subclasses of split graphs.
 
Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of \((2P_1+ P_3, K_4)\)-free graphs has bounded clique-width via a reduction to \(K_4\)-free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of H-free weakly chordal graphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
For a record see also the Information System on Graph Classes and their Inclusions [22].
 
2
This follows from results [15, 24, 31, 38] that assume the existence of a so-called c-expression of the input graph \(G\in \mathcal{G}\) combined with a result [37] that such a c-expression can be obtained in cubic time for some \(c\le 8^{\hbox {cw}(G)}-1\), where \(\hbox {cw}(G)\) is the clique-width of the graph G.
 
3
In Theorems 8, 9 and 10, we do not specify our upper bounds as this would complicate our proofs for negligible gain. In our proofs we repeatedly apply graph operations that exponentially increase the upper bound on the clique-width, which means that the bounds that could be obtained from our proofs would be very large and far from being tight. We use different techniques to prove Lemma 5 and Theorem 11, and these allow us to give good bounds for these cases.
 
Literature
1.
2.
go back to reference Boliac, R., Lozin, V.V.: On the clique-width of graphs in hereditary classes. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 44–54. Springer, Heidelberg (2002) CrossRef Boliac, R., Lozin, V.V.: On the clique-width of graphs in hereditary classes. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 44–54. Springer, Heidelberg (2002) CrossRef
3.
go back to reference Brandstädt, A.: (\(P_5\), diamond)-free graphs revisited: structure and linear time optimization. Discrete Appl. Math. 138(1–2), 13–27 (2004)MathSciNetCrossRefMATH Brandstädt, A.: (\(P_5\), diamond)-free graphs revisited: structure and linear time optimization. Discrete Appl. Math. 138(1–2), 13–27 (2004)MathSciNetCrossRefMATH
4.
go back to reference Brandstädt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the clique-width of \(H\)-free split graphs. In: Proceedings of EuroComb ENDM (to appear, 2015) Brandstädt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the clique-width of \(H\)-free split graphs. In: Proceedings of EuroComb ENDM (to appear, 2015)
5.
go back to reference Brandstädt, A., Engelfriet, J., Le, H.-O., Lozin, V.V.: Clique-width for 4-vertex forbidden subgraphs. Theor. Comput. Sys. 39(4), 561–590 (2006)MathSciNetCrossRefMATH Brandstädt, A., Engelfriet, J., Le, H.-O., Lozin, V.V.: Clique-width for 4-vertex forbidden subgraphs. Theor. Comput. Sys. 39(4), 561–590 (2006)MathSciNetCrossRefMATH
6.
go back to reference Brandstädt, A., Klembt, T., Mahfud, S.: \(P_6\)- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Math. Theor. Comput. Sci. 8(1), 173–188 (2006)MathSciNetMATH Brandstädt, A., Klembt, T., Mahfud, S.: \(P_6\)- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Math. Theor. Comput. Sci. 8(1), 173–188 (2006)MathSciNetMATH
7.
8.
go back to reference Brandstädt, A., Le, H.-O., Mosca, R.: Gem- and co-gem-free graphs have bounded clique-width. Int. J. Found. Comput. Sci. 15(1), 163–185 (2004)MathSciNetCrossRefMATH Brandstädt, A., Le, H.-O., Mosca, R.: Gem- and co-gem-free graphs have bounded clique-width. Int. J. Found. Comput. Sci. 15(1), 163–185 (2004)MathSciNetCrossRefMATH
9.
go back to reference Brandstädt, A., Le, H.-O., Mosca, R.: Chordal co-gem-free and (\(P_5\), gem)-free graphs have bounded clique-width. Discrete Appl. Math. 145(2), 232–241 (2005)MathSciNetCrossRefMATH Brandstädt, A., Le, H.-O., Mosca, R.: Chordal co-gem-free and (\(P_5\), gem)-free graphs have bounded clique-width. Discrete Appl. Math. 145(2), 232–241 (2005)MathSciNetCrossRefMATH
10.
go back to reference Brandstädt, A., Le, V.B., de Ridder, H.N.: Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes. Inf. Process. Lett. 89(4), 165–173 (2004)MathSciNetCrossRefMATH Brandstädt, A., Le, V.B., de Ridder, H.N.: Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes. Inf. Process. Lett. 89(4), 165–173 (2004)MathSciNetCrossRefMATH
11.
go back to reference Brandstädt, A., Mahfud, S.: Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Inf. Process. Lett. 84(5), 251–259 (2002)MathSciNetCrossRefMATH Brandstädt, A., Mahfud, S.: Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Inf. Process. Lett. 84(5), 251–259 (2002)MathSciNetCrossRefMATH
12.
go back to reference Brandstädt, A., Mosca, R.: On the structure and stability number of \(P_5\)- and co-chair-free graphs. Discrete Appl. Math. 132(1–3), 47–65 (2003)MathSciNetCrossRefMATH Brandstädt, A., Mosca, R.: On the structure and stability number of \(P_5\)- and co-chair-free graphs. Discrete Appl. Math. 132(1–3), 47–65 (2003)MathSciNetCrossRefMATH
13.
go back to reference Corneil, D.G., Habib, M., Lanlignel, J.-M., Reed, B.A., Rotics, U.: Polynomial-time recognition of clique-width \(\le 3\) graphs. Discrete Appl. Math. 160(6), 834–865 (2012)MathSciNetCrossRefMATH Corneil, D.G., Habib, M., Lanlignel, J.-M., Reed, B.A., Rotics, U.: Polynomial-time recognition of clique-width \(\le 3\) graphs. Discrete Appl. Math. 160(6), 834–865 (2012)MathSciNetCrossRefMATH
14.
15.
go back to reference Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Sys. 33(2), 125–150 (2000)MathSciNetCrossRefMATH Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Sys. 33(2), 125–150 (2000)MathSciNetCrossRefMATH
16.
17.
go back to reference Dabrowski, K.K., Golovach, P.A., Paulusma, D.: Colouring of graphs with Ramsey-type forbidden subgraphs. Theoret. Comput. Sci. 522, 34–43 (2014)MathSciNetCrossRefMATH Dabrowski, K.K., Golovach, P.A., Paulusma, D.: Colouring of graphs with Ramsey-type forbidden subgraphs. Theoret. Comput. Sci. 522, 34–43 (2014)MathSciNetCrossRefMATH
18.
go back to reference Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding clique-width via perfect graphs. In: Dediu, A.-H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 676–688. Springer, Heidelberg (2015) Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding clique-width via perfect graphs. In: Dediu, A.-H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 676–688. Springer, Heidelberg (2015)
19.
go back to reference Dabrowski, K.K., Lozin, V.V., Raman, R., Ries, B.: Colouring vertices of triangle-free graphs without forests. Discrete Math. 312(7), 1372–1385 (2012)MathSciNetCrossRefMATH Dabrowski, K.K., Lozin, V.V., Raman, R., Ries, B.: Colouring vertices of triangle-free graphs without forests. Discrete Math. 312(7), 1372–1385 (2012)MathSciNetCrossRefMATH
20.
go back to reference Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of \({H}\)-free bipartite graphs. Discrete Appl. Math. (to appear) Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of \({H}\)-free bipartite graphs. Discrete Appl. Math. (to appear)
21.
go back to reference Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 167–181. Springer, Heidelberg (2015) CrossRef Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 167–181. Springer, Heidelberg (2015) CrossRef
24.
go back to reference Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117–128. Springer, Heidelberg (2001) CrossRef Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117–128. Springer, Heidelberg (2001) CrossRef
25.
go back to reference Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-Complete. SIAM J. Discrete Math. 23(2), 909–939 (2009)MathSciNetCrossRefMATH Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-Complete. SIAM J. Discrete Math. 23(2), 909–939 (2009)MathSciNetCrossRefMATH
27.
go back to reference Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland Publishing Company, Amsterdam (2014)MATH Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland Publishing Company, Amsterdam (2014)MATH
28.
go back to reference Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(03), 423–443 (2000)MathSciNetCrossRefMATH Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(03), 423–443 (2000)MathSciNetCrossRefMATH
29.
go back to reference Gurski, F.: Graph operations on clique-width bounded graphs. CoRR, abs/cs/0701185 (2007) Gurski, F.: Graph operations on clique-width bounded graphs. CoRR, abs/cs/0701185 (2007)
30.
go back to reference Kamiński, M., Lozin, V.V., Milanič, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747–2761 (2009)MathSciNetCrossRefMATH Kamiński, M., Lozin, V.V., Milanič, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747–2761 (2009)MathSciNetCrossRefMATH
31.
go back to reference Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Appl. Math. 126(2–3), 197–221 (2003)MathSciNetCrossRefMATH Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Appl. Math. 126(2–3), 197–221 (2003)MathSciNetCrossRefMATH
33.
go back to reference Le, H.-O.: Contributions to clique-width of graphs. Ph.D. thesis, University of Rostock (2003). Cuvillier Verlag Göttingen (2004) Le, H.-O.: Contributions to clique-width of graphs. Ph.D. thesis, University of Rostock (2003). Cuvillier Verlag Göttingen (2004)
34.
go back to reference Lozin, V.V., Rautenbach, D.: On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18(1), 195–206 (2004)MathSciNetCrossRefMATH Lozin, V.V., Rautenbach, D.: On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18(1), 195–206 (2004)MathSciNetCrossRefMATH
35.
go back to reference Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few \(P_4\)’s. Int. J. Found. Comput. Sci. 10(03), 329–348 (1999)MathSciNetCrossRefMATH Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few \(P_4\)’s. Int. J. Found. Comput. Sci. 10(03), 329–348 (1999)MathSciNetCrossRefMATH
38.
go back to reference Rao, M.: MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoret. Comput. Sci. 377(1–3), 260–267 (2007)MathSciNetCrossRefMATH Rao, M.: MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoret. Comput. Sci. 377(1–3), 260–267 (2007)MathSciNetCrossRefMATH
Metadata
Title
Bounding the Clique-Width of H-free Chordal Graphs
Authors
Andreas Brandstädt
Konrad K. Dabrowski
Shenwei Huang
Daniël Paulusma
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-48054-0_12

Premium Partner