\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Tom\'as Feder, Pavol Hell and Wing Xie}
%
%
\medskip
\noindent
%
%
{\bf Matrix Partitions with Finitely Many Obstructions}
%
%
\vskip 5mm
\noindent
%
%
%
%
Each $m$ by $m$ symmetric matrix $M$ over $0, 1, *$, defines
a partition problem, in which an input graph $G$ is to be
partitioned into $m$ parts with adjacencies governed by $M$,
in the sense that two distinct vertices in (possibly equal)
parts $i$ and $j$ are adjacent if $M(i,j)=1$, and nonadjacent
if $M(i,j)=0$. (The entry $*$ implies no restriction.)
We ask which matrix partition problems admit a characterization
by a finite set of forbidden induced subgraphs. We prove that
matrices containing a certain two by two diagonal submatrix $S$
never have such characterizations. We then develop a recursive
technique that allows us (with some extra effort) to verify that
matrices without $S$ of size five or less always have a finite
forbidden induced subgraph characterization. However, we exhibit
a six by six matrix without $S$ which cannot be characterized by
finitely many induced subgraphs. We also explore the connection
between finite forbidden subgraph characterizations and related
questions on the descriptive and computational complexity of
matrix partition problems.
\bye