Matrix partitions with finitely many obstructions

MaRDI QIDQ1010616zbMATH OpenFDO

Authors Tomás Feder, Pavol Hell, Wing Xie

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129715, http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r58.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

forbidden subgraphsgeneralized colouringsmatrix partitions

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• Matrix Partitions with Finitely Many Obstructions
• Matrix partitions of perfect graphs
• Matrix partitions of split graphs
• Obstructions to partitions of chordal graphs
• Almost all friendly matrices have many obstructions

Cited in

(17)

• Adaptable chromatic number of graph products
• The monotonicity property of \(M\)-partition problems
• Partitions of matrix spaces with an application to \(q\)-rook polynomials
• Dichotomy for tree-structured trigraph list homomorphism problems
• Matrix partitions of perfect graphs
• Graph partitions with prescribed patterns
• Matrix partitions of split graphs
• Counting 4 4 matrix partitions of graphs
• Matrix Partitions with Finitely Many Obstructions
• Adapted list coloring of planar graphs
• The Editor's Corner: Finite Lists of Obstructions
• Obstructions to partitions of chordal graphs
• Adapted game colouring of graphs
• Almost all friendly matrices have many obstructions
• scientific article; zbMATH DE number 6281797 (Why is no real title available?)
• Generalisations of matrix partitions: complexity and obstructions
• Digraph matrix partitions and trigraph homomorphisms

This page was built for publication: Matrix partitions with finitely many obstructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010616)