×

Graph partitions with prescribed patterns. (English) Zbl 1292.05214

Summary: We discuss partition problems that generalize graph colouring and homomorphism problems, and occur frequently in the study of perfect graphs. Depending on the pattern, we seek a finite forbidden induced subgraph characterization, or at least a polynomial time algorithm. We give an overview of the current knowledge, focusing on open problems and recent breakthroughs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alekseev, V. E.; Farrugia, A.; Lozin, V. V., New results on generalized graph coloring, Discrete Math. Theor. Comput. Sci., 6, 215-222 (2004) · Zbl 1059.05044
[2] Atserias, A., On digraph coloring problems and treewidth duality, European J. Combin., 29, 796-820 (2008) · Zbl 1160.05024
[3] Ball, R. N.; Nešetřil, J.; Pultr, A., Dualities in full homomorphisms, European J. Combin., 31, 106-119 (2010) · Zbl 1219.05092
[4] Bang-Jensen, J.; Hell, P., The effect of two cycles on the complexity of colouring by directed graphs, Discrete Appl. Math., 26, 1-23 (1990) · Zbl 0697.05029
[5] Bang-Jensen, J.; Hell, P.; MacGillivray, G., The complexity of colourings by semi-complete digraphs, SIAM J. Discrete Math., 1, 281-298 (1988) · Zbl 0678.05018
[6] Bang-Jensen, J.; Hell, P.; MacGillivray, G., On the complexity of colouring by superdigraphs of bipartite graphs, Discrete Math., 109, 27-44 (1992) · Zbl 0783.05047
[7] Bang-Jensen, J.; Hell, P.; MacGillivray, G., Hereditarily hard \(H\)-colouring problems, Discrete Math., 138, 75-92 (1995) · Zbl 0816.68090
[8] Barto, L.; Kozik, M.; Maróti, M.; Niven, T., CSP dichotomy for special triads, Proc. Amer. Math. Soc., 137, 2921-2934 (2009) · Zbl 1215.05179
[9] Barto, L.; Kozik, M.; Niven, T., The CSP dichotomy holds for digraphs with no sources and sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Comput., 38, 1782-1802 (2008) · Zbl 1191.68460
[10] Bodirsky, M.; Kara, J.; Martin, B., The complexity of surjective homomorphism problems—a survey · Zbl 1246.05104
[11] Brandstädt, A., Partitions of graphs into one or two independent stable sets and cliques, Discrete Math., 152, 47-54 (1996) · Zbl 0853.68140
[12] Brandstädt, A.; Hammer, P. L.; Le, V. B.; Lozin, V. V., Bisplit graphs, Discrete Math., 299, 11-32 (2005) · Zbl 1073.05059
[13] Brewster, R. B.; Feder, T.; Hell, P.; Huang, J.; MacGillivray, G., Near-unanimity functions and varieties of reflexive graphs, SIAM J. Discrete Math., 22, 938-960 (2008) · Zbl 1200.05217
[14] Bulatov, A. A., Tractable conservative constraint satisfaction problems, LICS, 321-330 (2003)
[15] Bulatov, A. A.; Krokhin, A.; Larose, B., Dualities for constraint satisfaction problems, (Complexity of Constraints. Complexity of Constraints, LNCS, vol. 5250 (2008)), 93-124 · Zbl 1171.68494
[16] Cameron, K.; Eschen, E. M.; Hoàng, C. T.; Sritharan, R., The complexity of the list partition problem for graphs, SIAM J. Discrete Math., 21, 900-929 (2007) · Zbl 1151.05045
[17] Chernyak, Z. A.; Chernyak, A. A., About recognizing polar graphs, Discrete Math., 62, 133-138 (1986) · Zbl 0606.05058
[18] Chudnovsky, M., Berge trigraphs, J. Graph Theory, 53, 1-55 (2006) · Zbl 1101.05036
[19] Chvátal, V., Star-cutsets and perfect graphs, J. Combin. Theory Ser. B, 39, 189-199 (1985) · Zbl 0674.05058
[20] Cook, K.; Dantas, S.; Eschen, E. M.; Faria, L.; de Figueiredo, C. M.H.; Klein, S., \(2 K_2\) partitions into non-empty parts, Discrete Math., 310, 1259-1264 (2010) · Zbl 1230.05233
[21] Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs on bounded clique width, Theory Comput. Syst., 33, 125-150 (2000) · Zbl 1009.68102
[23] Damaschke, P., Induced subgraphs and well-quasi-ordering, J. Graph Theory, 14, 427-435 (1990) · Zbl 0721.05059
[24] Dantas, S.; de Figueiredo, C. M.H.; Gravier, S.; Klein, S., Finding \(H\)-partitions efficiently, Theor. Inform. Appl., 39, 133-144 (2005) · Zbl 1063.05124
[25] de Figueiredo, C. M.H., The \(P\) versus NP-complete dichotomy of some challenging problems in graph theory, Discrete Applied Math., 160, 2681-2693 (2012) · Zbl 1253.68268
[26] de Figueiredo, C. M.H.; Klein, S., The NP-completeness of multipartite cutset testing, Congr. Numer., 119, 217-222 (1996) · Zbl 0897.68070
[27] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[28] Ekim, T.; Hell, P.; Stacho, J.; de Werra, D., Polarity of chordal graphs, Discrete Appl. Math., 156, 2469-2479 (2008) · Zbl 1163.05051
[31] Erdös, P., Graph theory and probability, Canad. J. Math., 11, 34-38 (1959) · Zbl 0084.39602
[32] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Combin. Theory Ser. B, 72, 236-250 (1998) · Zbl 0904.05078
[33] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 230-246 (2006) · Zbl 1111.68115
[34] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Math., 306, 2450-2460 (2006) · Zbl 1143.05035
[35] Feder, T.; Hell, P., On realizations of point determining graphs and obstructions to full homomorphisms, Discrete Math., 308, 1639-1652 (2008) · Zbl 1135.05042
[37] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings of cographs, (Graph Theory in Paris (2006), Birkhauser Verlag), 149-167 · Zbl 1114.05060
[38] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[39] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[40] Feder, T.; Hell, P.; Huang, J., List homomorphisms of graphs with bounded degrees, Discrete Math., 307, 386-392 (2007) · Zbl 1111.05035
[41] Feder, T.; Hell, P.; Huang, J., Extension problems with degree bounds, Discrete Appl. Math., 157, 1592-1599 (2009) · Zbl 1177.05037
[42] Feder, T.; Hell, P.; Jonsson, P.; Krokhin, A.; Nordh, G., Retractions to pseudo-forests, SIAM J. Discrete Math., 24, 101-112 (2010) · Zbl 1215.05063
[43] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[44] Feder, T.; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., List matrix partitions of chordal graphs, Theoret. Comput. Sci., 349, 52-66 (2005) · Zbl 1084.05026
[47] Feder, T.; Hell, P.; Nekooei Rizi, S., Obstructions to partitions of chordal graphs, Discrete Math. (2012), in press (online version) · Zbl 1277.05137
[48] Feder, T.; Hell, P.; Stacho, J.; Schell, G., Dichotomy for tree-structured trigraph list homomorphism problems, Discrete Appl. Math., 159, 1217-1224 (2011) · Zbl 1223.05095
[49] Feder, T.; Hell, P.; Stacho, J.; Schell, G., Dichotomy for tree-structured matrix partition problems, Discrete Appl. Math., 159, 1217-1224 (2011) · Zbl 1223.05095
[50] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Appl. Math., 154, 2458-2469 (2006) · Zbl 1106.05060
[51] Feder, T.; Hell, P.; Xie, W., Matrix partitions with finitely many obstructions, Electron. J. Combin., 14, R58 (2007) · Zbl 1158.05326
[52] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction, SIAM J. Comput., 28, 57-104 (1999) · Zbl 0914.68075
[53] Fleischner, H.; Mujuni, E.; Paulusma, D.; Szeider, S., Covering graphs with few complete bipartite subgraphs, Theoret. Comput. Sci., 410, 2045-2053 (2009) · Zbl 1168.68019
[54] Foldes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315 (1977)
[55] Galluccio, A.; Hell, P.; Nešetřil, J., The complexity of \(H\)-colouring of bounded degree graphs, Discrete Math., 222, 101-109 (2000) · Zbl 0956.05036
[56] Golovach, P. A.; Paulusma, D.; Song, J., Computing surjective homomorphisms to partially reflexive trees, (CSR 2011 Proceedings. CSR 2011 Proceedings, LNCS, vol. 6651 (2011)), 261-274 · Zbl 1332.68073
[57] Hell, P., Algorithmic aspects of graph homomorphisms, (Wensley, C. D., Surveys in Combinatorics 2003. Surveys in Combinatorics 2003, London Math. Soc. Lecture Note Series, vol. 307 (2013), Cambridge University Press), 239-276 · Zbl 1035.05089
[59] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097
[60] Hell, P.; Klein, S.; Protti, F.; Tito, L., On generalized split graphs, Electron. Notes Discrete Math., 7, 98-101 (2001) · Zbl 0981.05076
[61] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[62] Hell, P.; Nešetřil, J., Counting list homomorphisms and graphs with bounded degrees, (Nešetřil, J.; Winkler, P., Graphs, Morphisms and Statistical Physics. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 63 (2004)), 105-112 · Zbl 1059.05049
[63] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford Univ. Press · Zbl 1062.05139
[64] Hell, P.; Nešetřil, J., Colouring, constraint satisfaction, and complexity, Comput. Sci. Rev., 2, 143-163 (2008) · Zbl 1302.68251
[65] Hell, P.; Nešetřil, J.; Zhu, X., Complexity of tree homomorphisms, Discrete Appl. Math., 70, 23-36 (1996) · Zbl 0868.05018
[66] Hell, P.; Nešetřil, J.; Zhu, X., Duality of graph homomorphisms, (Combinatorics, Paul Erdös is Eighty. Combinatorics, Paul Erdös is Eighty, Bolyai Society Math. Studies, vol. 2 (1996)), 271-282 · Zbl 0846.05093
[67] Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc., 348, 147-156 (1996) · Zbl 0877.05055
[69] Hell, P.; Rival, I., Absolute retracts and varieties of reflexive graphs, Canad. J. Math., 39, 544-567 (1987) · Zbl 0627.05039
[70] Hell, P.; Zhu, X., Homomorphisms to oriented paths, Discrete Math., 132, 107-114 (1994) · Zbl 0819.05030
[71] Ito, T.; Kaminski, M.; Paulusma, D.; Thilikos, D. M., On disconnected cuts and separators, Discrete Appl. Math., 159, 1345-1351 (2011) · Zbl 1223.05155
[72] Kennedy, W. S.; Reed, B., Fast skew partition recognition, (CGGT 2007 Proceedings. CGGT 2007 Proceedings, LNCS, vol. 4535 (2008)), 101-107 · Zbl 1162.05359
[73] Kun, G.; Nešetřil, J., NP for combinatorialists, Electron. Notes Discrete Math., 29, 373-381 (2007) · Zbl 1341.05100
[74] Larose, B.; Loten, C.; Tardif, C., A characterization of first-order constraint satisfaction problems, Logical Methods Comput. Sci., 3, 4 (2007), (electronic) · Zbl 1131.68098
[75] Martin, B.; Paulusma, D., The computational complexity of disconnected cut and 2K2-partition, LNCS, 6876, 561-575 (2011)
[77] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterising gaps and good characterizations), J. Combin. Theory Ser. B, 80, 80-97 (2000) · Zbl 1024.05078
[78] Nešetřil, J.; Tardif, C., Short answers to exponentially long questions: extremal aspects of homomorphism duality, SIAM J. Discrete Math., 19, 914-920 (2005) · Zbl 1105.05025
[79] Rossman, B., Homomorphism preservation theorems, J. ACM, 55, 1-53 (2008) · Zbl 1326.03038
[80] Siggers, M. H., A new proof of the \(H\)-colouring dichotomy, SIAM J. Discrete Math., 23, 2204-2210 (2010) · Zbl 1207.05065
[81] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[83] Vikas, N., Computational complexity of compaction to reflexive cycles, SIAM J. Comput., 32, 253-280 (2003) · Zbl 1029.68085
[85] Vikas, N., Algorithms for partition of some class of graphs under compaction, (COCOON 2011 Proceedings. COCOON 2011 Proceedings, LNCS, vol. 6842 (2011)), 319-330 · Zbl 1353.05119
[86] Whitesides, S., An algorithm for finding clique cutsets, Inform. Process. Lett., 12, 31-32 (1981) · Zbl 0454.68078
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.