Feder, Tomás; Hell, Pavol; Shklarsky, Oren Matrix partitions of split graphs. (English) Zbl 1283.05213 Discrete Appl. Math. 166, 91-96 (2014). Summary: Matrix partition problems generalize a number of natural graph partition problems, and have been studied for several standard graph classes. We prove that each matrix partition problem has only finitely many minimal obstructions for split graphs. Previously such a result was only known for the class of cographs. (In particular, there are matrix partition problems which have infinitely many minimal chordal obstructions.) We provide (close) upper and lower bounds on the maximum size of a minimal split obstruction. This shows for the first time that some matrices have exponential-sized minimal obstructions of any kind (not necessarily split graphs). We also discuss matrix partitions for bipartite and co-bipartite graphs. Cited in 4 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C15 Coloring of graphs and hypergraphs 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) Keywords:generalized graph colouring; matrix partition; split graphs; minimal obstructions; forbidden subgraphs PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Appl. Math. 166, 91--96 (2014; Zbl 1283.05213) Full Text: DOI arXiv References: [1] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Math., 306, 19-20, 2450-2460 (2006) · Zbl 1143.05035 [2] Feder, T.; Hell, P., On realizations of point determining graphs, and obstructions to full homomorphisms, Discrete Math., 308, 9, 1639-1652 (2008) · Zbl 1135.05042 [3] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings (matrix partitions) of cographs, (Graph Theory in Paris (2006), Birkhauser Verlag), 149-167 · Zbl 1114.05060 [4] Feder, T.; Hell, P.; Klein, Sulamita; Motwani, Rajeev, List partitions, SIAM J. Discrete Math., 16, 3, 449 (2003) · Zbl 1029.05143 [5] 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 [6] Feder, T.; Hell, P.; Nekooei Rizi, S., Obstructions to partitions of chordal graphs, Discrete Math., 313, 1861-1871 (2013) · Zbl 1277.05137 [7] Feder, T.; Hell, P.; Xie, W., Matrix partitions with finitely many obstructions, Electron. J. Combin., 14 (2007) · Zbl 1158.05326 [8] Földes, S.; Hammer, P. L., Split graphs, (Hoffman, F.; etal., Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing (1977), Louisiana State Univ.: Louisiana State Univ. Baton Rouge, Louisiana), 311-315, As cited in Golumbic 2004 [9] Hell, P., Graph partitions with prescribed patterns, European J. Combin., 35, 335-353 (2014) · Zbl 1292.05214 [10] König, D., Theorie der Endlichen und Unendlichen Graphen (1936), As cited in West, 2001 · JFM 62.0654.05 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.