×

Matrix partitions with finitely many obstructions. (English) Zbl 1158.05325

Hliněný, Petr (ed.) et al., 6th Czech-Slovak international symposium on combinatorics, graph theory, algorithms and applications, DIMATIA Center, Charles University, Prague, Czech Republic, July 10–16, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 28, 371-378 (2007).
Summary: We ask which matrix partition problems admit a characterization by a finite set of forbidden induced subgraphs. We prove some positive and some negative results; these are sufficient to classify all such problems with matrices of size up to five. We also consider related questions on the descriptive and computational complexity of matrix partition problems. [See also the authors’ article in Electron. J. Comb. 14, No. 1, Research Paper R58, 17 p. (2007; Zbl 1158.05326).]
For the entire collection see [Zbl 1109.05007].

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A99 Basic linear algebra
05C75 Structural characterization of families of graphs

Citations:

Zbl 1158.05326
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Atserias, “On Digraph coloring problems and treewidth duality”, mansucript 2006; A. Atserias, “On Digraph coloring problems and treewidth duality”, mansucript 2006 · Zbl 1160.05024
[2] R.N. Ball, J. Nešetřil, and A. Pultr, “Dualities in full homomorphisms”, mansucript 2006; R.N. Ball, J. Nešetřil, and A. Pultr, “Dualities in full homomorphisms”, mansucript 2006
[3] K. Cameron, E.E. Eschen, C.T. Hoang and R. Sritharan, “The list partition problem for graphs,” Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, 391-399; K. Cameron, E.E. Eschen, C.T. Hoang and R. Sritharan, “The list partition problem for graphs,” Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, 391-399 · Zbl 1318.05072
[4] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, “The strong perfect graph theorem”, to appear in the Annals of Math; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, “The strong perfect graph theorem”, to appear in the Annals of Math · Zbl 1112.05042
[5] Chvátal, V., Star-cutsets and perfect graphs, J. Combinatorial Theory B, 39, 189-199 (1985) · Zbl 0674.05058
[6] Bruno Courcelle, “Graph Operations and Monadic Second-Order Logic: A Survey”, LPAR 2000 20-24; Bruno Courcelle, “Graph Operations and Monadic Second-Order Logic: A Survey”, LPAR 2000 20-24 · Zbl 0988.68559
[7] T. Feder and P. Hell, “Full constraint satisfaction problems”, SIAM J. on Computing, in press; T. Feder and P. Hell, “Full constraint satisfaction problems”, SIAM J. on Computing, in press · Zbl 1111.68115
[8] T. Feder and P. Hell, “Matrix partitions of perfect graphs”, Discrete Math., in press; T. Feder and P. Hell, “Matrix partitions of perfect graphs”, Discrete Math., in press · Zbl 1143.05035
[9] T. Feder and P. Hell, “On realizations of point determining graphs, and obstructions to full homomorphisms”, manuscript 2004; T. Feder and P. Hell, “On realizations of point determining graphs, and obstructions to full homomorphisms”, manuscript 2004 · Zbl 1135.05042
[10] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of list partitions, SIAM J. Discrete Mathematics, 16, 449-478 (2003) · Zbl 1029.05143
[11] Feder, T.; Hell, P.; Klein, S.; Nogueira, L.; Protti, F., List matrix partitions of chordal graphs, Theoretical Computer Science, 349, 52-66 (2005) · Zbl 1084.05026
[12] T. Feder, P. Hell, D. Kral, and J. Sgall, “Two algorithms for list matrix partitions.” Symposium on Discrete Algorithms 2005; T. Feder, P. Hell, D. Kral, and J. Sgall, “Two algorithms for list matrix partitions.” Symposium on Discrete Algorithms 2005 · Zbl 1297.68091
[13] T. Feder, P. Hell, and K. Tucker-Nally, “Digraph matrix partitions and trigraph homomorphisms”, manuscript 2004; T. Feder, P. Hell, and K. Tucker-Nally, “Digraph matrix partitions and trigraph homomorphisms”, manuscript 2004 · Zbl 1106.05060
[14] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings (matrix partitions) of cographs, (Ramirez, J., Graph Theory. Graph Theory, Volume in Memory of Claude Berge, Trend in Mathematics (2006), Birkhäuser Verlag: Birkhäuser Verlag Basel), 149-167 · Zbl 1114.05060
[15] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput., 28, 236-250 (1998), (ALSO in STOC 25 (1993) 612-622) · Zbl 0914.68075
[16] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[17] Dantas, S.; de Figueiredo, C. M.H.; Gravier, S.; Klein, S., Finding H-partitions efficiently, Theoret. Informatics Appl., 39, 133-144 (2005) · Zbl 1063.05124
[18] Foldes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315 (1977)
[19] Hell, P.; Klein, S.; Tito Nogueira, L.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Applied Math., 141, 185-194 (2004) · Zbl 1043.05097
[20] Hell, P.; Nešetřil, J., On the complexity of \(H\)-coloring, J. Comb. Theory, Series B, 48, 92-110 (1990) · Zbl 0639.05023
[21] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[22] B. Rossman, “Existential positive types and preservation under homomorphisms”, 20th IEEE LICS (2005); B. Rossman, “Existential positive types and preservation under homomorphisms”, 20th IEEE LICS (2005)
[23] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[24] W. Xie, “Forbidden subgraph characterizations of matrix partitions”, M. Sc. thesis, Simon Fraser University 2006; W. Xie, “Forbidden subgraph characterizations of matrix partitions”, M. Sc. thesis, Simon Fraser University 2006
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.