Matrix partitions with finitely many obstructions (Q1010616)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Matrix partitions with finitely many obstructions
scientific article

    Statements

    Matrix partitions with finitely many obstructions (English)
    0 references
    0 references
    0 references
    0 references
    7 April 2009
    0 references
    Summary: 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.
    0 references
    matrix partitions
    0 references
    forbidden subgraphs
    0 references
    generalized colourings
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references