Feder, Tomás; Hell, Pavol; Nekooei Rizi, Shekoofeh Obstructions to partitions of chordal graphs. (English) Zbl 1277.05137 Discrete Math. 313, No. 19, 1861-1871 (2013). Summary: Matrix partition problems generalize graph colouring and homomorphism problems, and occur frequently in the study of perfect graphs. It is difficult to decide, even for a small matrix \(M\), whether the \(M\)-partition problem is polynomial time solvable or NP-complete (or possibly neither), and whether \(M\)-partitionable graphs can be characterized by a finite set of forbidden induced subgraphs (or perhaps by some other first order condition). We discuss these problems for the class of chordal graphs. In particular, we classify all small matrices \(M\) according to whether \(M\)-partitionable graphs have finitely or infinitely many minimal chordal obstructions (for all matrices of size less than four), and whether they admit a polynomial time recognition algorithm or are NP-complete (for all matrices of size less than five). We also suggest questions about larger matrices. Cited in 4 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C17 Perfect graphs 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q25 Analysis of algorithms and problem complexity Keywords:graph partitions; graph homomorphisms; forbidden subgraph characterizations; chordal graphs; perfect graphs PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Math. 313, No. 19, 1861--1871 (2013; Zbl 1277.05137) Full Text: DOI References: [1] Atserias, A., On digraph coloring problems and treewidth duality, European J. Combin., 29, 796-820 (2008) · Zbl 1160.05024 [2] 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 [3] Chvátal, V., Star-cutsets and perfect graphs, J. Combin. Theory Ser. B, 39, 189-199 (1985) · Zbl 0674.05058 [5] Damaschke, P., Induced subgraphs and well-quasi-ordering, J. Graph Theory, 14, 427-435 (1990) · Zbl 0721.05059 [6] Dantas, S.; de Figueiredo, C. M.H.; Gravier, S.; Klein, S., Finding \(H\)-partition problems, Theor. Inform. Appl., 39, 133-144 (2005) · Zbl 1063.05124 [7] de Figueiredo, C. M.H.; Klein, S., The NP-completeness of multipartite cutset testing, Congr. Numer., 119, 217-222 (1996) · Zbl 0897.68070 [8] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107 [9] Färnqvist, T.; Jonsson, P., Bounded tree-width and CSP-related problems, (Tokuyama, T., Proceedings of the 18th International Conference on Algorithms and Computation, ISAAC’07 (2007), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 632-643 · Zbl 1193.68130 [10] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 230-246 (2006) · Zbl 1111.68115 [11] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Math., 306, 2450-2460 (2006) · Zbl 1143.05035 [12] Feder, T.; Hell, P., On realizations of point determining graphs and obstructions to full homomorphisms, Discrete Math., 308, 1639-1652 (2008) · Zbl 1135.05042 [13] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings of cographs, (Graph Theory in Paris (2006), Birkhäuser Verlag), 149-167 [14] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143 [15] 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 [16] Feder, T.; Hell, P.; Nekooei Rizi, S., Partitioning chordal graphs, Electron. Notes Discrete Math., 38, 325-330 (2011) · Zbl 1274.05376 [17] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Appl. Math., 154, 2458-2469 (2006) · Zbl 1106.05060 [18] Feder, T.; Hell, P.; Xie, W., Matrix partitions with finitely many obstructions, Electron. J. Combin., 14, R58 (2007) · Zbl 1158.05326 [19] 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 [20] Foldes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315 (1977) [21] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 [23] 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 [24] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford Univ. Press · Zbl 1062.05139 [25] Hell, P.; Nešetřil, J., Colouring, constraint satisfaction, and complexity, Comput. Sci. Rev., 2, 143-163 (2008) · Zbl 1302.68251 [26] Kennedy, W. S.; Reed, B., Fast skew cutset recognition, (Computational Geometry and Graph Theory. Computational Geometry and Graph Theory, Lecture Notes in Computer Science, vol. 4535 (2008)), 101-107 · Zbl 1162.05359 [27] Martin, B.; Paulusma, D., The computational complexity of disconnected cut and 2K2-partition, (Lee, Jimmy, Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming. Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, CP’11. Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming. Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, CP’11, Lecture Notes in Computer Science, vol. 6876 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 561-575 [29] Rossman, B., Homomorphism preservation theorems, J. ACM, 55, 1-53 (2008) · Zbl 1326.03038 [30] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039 [31] Vikas, N., Computational complexity of compaction to reflexive cycles, SIAM J. Comput., 32, 253-280 (2003) · Zbl 1029.68085 [32] Vikas, N., Algorithms for partition of some class of graphs under compaction, (Computing and Combinatorics. Computing and Combinatorics, Lecture Notes in Computer Science, vol. 6842 (2011)), 319-330 · Zbl 1353.05119 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.