Recent developments on graphs of bounded clique-width. (English) Zbl 1211.05165
Summary: Whether the clique-width of graphs in a certain class of graphs is bounded or not, is an important question from an algorithmic point of view, as many problems that are NP-hard in general admit polynomial-time solutions when restricted to graphs of bounded clique-width. Over the last few years, many classes of graphs have been shown to have bounded clique-width. For many others, this parameter has been proved to be unbounded. This paper provides a survey of recent results addressing this problem.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 03B25 | Decidability of theories and sets of sentences |
| 03B70 | Logic in computer science |
| 05C40 | Connectivity |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Alekseev, V., On lower layers of the lattice of hereditary classes of graphs, Diskretnyiˇ Analizi Issledovanie Operatsiiˇ Seriya, 4, 1, 3-12 (1997), (in Russian) · Zbl 0880.05051 |
| [2] | Bodlaender, H. L.; Thilikos, D. M., Treewidth for graphs with small chordality, Discrete Applied Mathematics, 79, 45-61 (1997) · Zbl 0895.68113 |
| [3] | Boliac, R.; Lozin, V. V., An attractive class of bipartite graphs, Discussiones Mathematicae Graph Theory, 2, 293-301 (2001) · Zbl 1002.05060 |
| [4] | Boliac, R.; Lozin, V., On the clique-width of graphs in hereditary classes, Lecture Notes in Computer Science, 2518, 44-54 (2002) · Zbl 1020.05046 |
| [5] | Bollobás, B., Extremal Graph Theory (1978), Academic Press, Inc.: Academic Press, Inc. London · Zbl 0419.05031 |
| [6] | Brandstädt, A.; Le, H.-O.; de Ridder, N. H., Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, Information Processing Letters, 89, 165-173 (2004) · Zbl 1176.05076 |
| [7] | Brandstädt, A.; Dragan, F.; Le, H.-O.; Mosca, R., New graph classes of bounded clique-width, Theory of Computing Systems, 38, 623-645 (2005) · Zbl 1084.68088 |
| [8] | Brandstädt, A.; Lozin, V. V., On the linear structure and clique-width of bipartite permutation graphs, Ars Combinatoria, 67, 273-289 (2003) · Zbl 1076.05066 |
| [9] | Brandstädt, A.; Le, H.-O.; Mosca, R., Chordal co-gem-free and \((P_5, gem)\)-free graphs have bounded clique-width, Discrete Applied Mathematics, 145, 232-241 (2005) · Zbl 1084.05056 |
| [10] | Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V. V., Clique-width for four-vertex forbidden subgraphs, Theory of Computing Systems, 34, 561-590 (2006) · Zbl 1103.68088 |
| [11] | Brandstädt, A.; Klembt, T.; Mahfud, S., \(P_6\)- and triangle-free graphs revisited: Structure and bounded clique-width, Discrete Mathematics and Theoretical Computer Science, 8, 173-188 (2006) · Zbl 1153.05040 |
| [12] | Corneil, D. G.; Lerchs, H.; Burlingham, L. Stewart, Complement reducible graphs, Discrete Applied Mathematics, 3, 163-174 (1981) · Zbl 0463.05057 |
| [13] | Corneil, D. G.; Perl, Y.; Stewart, L. K., Cographs: Recoginiton, applications, and algorithms, Congressus Numerantium, 43, 249-258 (1984) · Zbl 0563.05049 |
| [14] | Corneil, D. G.; Habib, M.; Lanlignel, J. M.; Reed, B.; Rotics, U., Polynomial time recognition of clique-width at most three graphs, (Proceedings of Latin American Symposium on Theoretical Informatics (LATIN’2000). Proceedings of Latin American Symposium on Theoretical Informatics (LATIN’2000), Lecture Notes in Computer Science, vol. 1776 (2000), Springer-Verlag) |
| [15] | Corneil, D. G.; Rotics, U., On the relationship between clique-width and treewidth, SIAM Journal on Computing, 34, 825-847 (2005) · Zbl 1069.05067 |
| [16] | Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1 (1997), World Sci. Publishing: World Sci. Publishing River Edge, NJ), 313-400 · Zbl 0908.68095 |
| [17] | Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, 46, 218-270 (1993) · Zbl 0825.68446 |
| [18] | Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory of Computing Systems, 33, 125-150 (2000) · Zbl 1009.68102 |
| [19] | Courcelle, B.; Olariu, S., Upper bounds to the clique-width of a graph, Discrete Applied Mathematics, 101, 77-114 (2000) · Zbl 0958.05105 |
| [20] | Demaine, E. D.; Hajiaghayi, M. T., Diameter and treewidth in minor-closed graph families, revisited, Algorithmica, 40, 211-215 (2004) · Zbl 1082.05086 |
| [21] | Eppstein, D., Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 275-291 (2000) · Zbl 0963.05128 |
| [22] | Erdős, P.; Spencer, J., Probabilistic methods in combinatorics, (Probability and Mathematical Statistics, vol. 17 (1974), Academic Press: Academic Press New York-London) · Zbl 0308.05001 |
| [23] | Espelage, W.; Gurski, F.; Wanke, E., How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time, Lecture Notes in Computer Science, 2204, 117-128 (2001) · Zbl 1042.68626 |
| [24] | M.R. Fellows, F.A. Rosamond, U. Rotics, S. Szeider, Clique-width Minimization is NP-hard, in: Proceedings of 38th ACM Symposium on Theory of Computing, 2006, pp. 354-362; M.R. Fellows, F.A. Rosamond, U. Rotics, S. Szeider, Clique-width Minimization is NP-hard, in: Proceedings of 38th ACM Symposium on Theory of Computing, 2006, pp. 354-362 · Zbl 1301.68145 |
| [25] | Foldes, S.; Hammer, P. L., Split graphs, Congressus Numerantium, 19, 311-315 (1977) · Zbl 0407.05071 |
| [26] | M.C. Golumbic, U. Rotics, The clique-width of unit interval graphs is unbounded, in: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999). Congressus Numerantium 140, 1999, pp. 5-17; M.C. Golumbic, U. Rotics, The clique-width of unit interval graphs is unbounded, in: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999). Congressus Numerantium 140, 1999, pp. 5-17 · Zbl 0960.05075 |
| [27] | Golumbic, M. C.; Rotics, U., On the clique-width of some perfect graph classes, International Journal of Foundations of Computer Science, 11, 423-443 (2000) · Zbl 1320.05090 |
| [28] | Gurski, F.; Wanke, E., The tree-width of clique-width bounded graphs without \(K_{n, n}\), Lecture Notes in Computer Science, 1928, 196-205 (2000) · Zbl 0988.68131 |
| [29] | Gurski, F.; Wanke, E., Line graphs of bounded clique-width, Discrete Mathematics, 307, 2734-2754 (2007) · Zbl 1128.05049 |
| [30] | C.T. Hoàng, Perfect graphs, Ph.D. Thesis, School of Computer Science, McGill University, Montreal, 1985; C.T. Hoàng, Perfect graphs, Ph.D. Thesis, School of Computer Science, McGill University, Montreal, 1985 |
| [31] | Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J., A new series of dense graphs of high girth, Bulletin of the AMS, 32, 73-79 (1995) · Zbl 0822.05039 |
| [32] | Kobler, D.; Rotics, U., Edge dominating set and colorings on graphs with fixed clique-width, Discrete Applied Mathematics, 126, 197-221 (2003) · Zbl 1009.05103 |
| [33] | Lozin, V. V., Bipartite graphs without a skew star, Discrete Mathematics, 257, 83-100 (2002) · Zbl 1010.05067 |
| [34] | Lozin, V.; Rautenbach, D., On the band-, tree- and clique-width of graphs with bounded vertex degree, SIAM Journal of Discrete Mathematics, 18, 195-206 (2004) · Zbl 1081.05098 |
| [35] | Lozin, V.; Rautenbach, D., Chordal bipartite graphs of bounded tree- and clique-width, Discrete Mathematics, 283, 151-158 (2004) · Zbl 1044.05060 |
| [36] | Lozin, V.; Rautenbach, D., The tree- and clique-width of bipartite graphs in special classes, Australasian Journal of Combinatorics, 34, 57-67 (2006) · Zbl 1102.68098 |
| [37] | Lozin, V. V.; Rudolf, G., Minimal universal bipartite graphs, Ars Combinatoria, 84, 345-356 (2007) · Zbl 1212.05255 |
| [38] | Lozin, V. V.; Volz, J., The clique-width of bipartite graphs in monogenic classes, International Journal of Foundations of Computer Science, 19, 477-494 (2008) · Zbl 1155.68057 |
| [39] | Makowsky, J. A.; Rotics, U., On the clique-width of graphs with few \(P_4\)’s, International Journal of Foundations of Computer Science, 10, 329-348 (1999) · Zbl 1320.05096 |
| [40] | Oum, S.-i., Rank-width and vertex minors, Journal of Combinatorial Theory Series B, 95, 79-100 (2005) · Zbl 1070.05023 |
| [41] | Oum, S.-i.; Seymour, P., Approximating clique-width and branch-width, Journal of Combinatorial Theory Series B, 94, 514-528 (2006) · Zbl 1114.05022 |
| [42] | Reed, B., Tree width and tangles: A new connectivity measure and some applications, (London Math. Soc. Lecture Note, vol. 241 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 87-162 · Zbl 0895.05034 |
| [43] | Robertson, N.; Seymour, P. D., Graph minors. I. Excluding a forest, Journal of Combinatorial Theory Series B, 35, 39-61 (1983) · Zbl 0521.05062 |
| [44] | Robertson, N.; Seymour, P. D., Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, 7, 309-322 (1986) · Zbl 0611.05017 |
| [45] | Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, 41, 92-114 (1986) · Zbl 0598.05055 |
| [46] | Scheinerman, E. R.; Zito, J., On the size of hereditary classes of graphs, Journal of Combinatorial Theory Series, 61, 16-39 (1994) · Zbl 0811.05048 |
| [47] | Seidel, J. J., A survey of two-graphs, (Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I. Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I, Atti dei Convegni Lincei, No. 17 (1976), Accad. Naz. Lincei: Accad. Naz. Lincei Rome), 481-511 · Zbl 0352.05016 |
| [48] | Spinrad, J. P., Nonredundant 1’s in \(\Gamma \)-free matrices, SIAM Journal of Discrete Mathematics, 8, 251-257 (1995) · Zbl 0837.05028 |
| [49] | Vanherpe, J.-M., Clique-width of partner-limited graphs, Discrete Mathematics, 276, 363-374 (2004) · Zbl 1031.05113 |
| [50] | Wanke, E., \(k\)-NLC graphs and polynomial algorithms, Discrete Applied Mathematics, 54, 251-266 (1994) · Zbl 0812.68106 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
