\input zb-basic
\input zb-ioport
\iteman{io-port 05158427}
\itemau{Feder, Tom\'as; Hell, Pavol; Xie, Wing}
\itemti{Matrix partitions with finitely many obstructions.}
\itemso{Hlin\v en\'y, 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).}
\itemab
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).]
\itemrv{~}
\itemcc{}
\itemut{matrix partitions; forbidden subgraphs; generalized colourings}
\itemli{doi:10.1016/j.endm.2007.01.057}
\end