Matrix partitions with finitely many obstructions
type: Item
instance of: scholarly article
title: Matrix partitions with finitely many obstructions
zbMATH Open document ID: 1158.05326
author: Tomás Feder
author: Pavol Hell
author: Wing Xie
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129715
full work available at URL: v14i1r58.html
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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A99
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5540836
zbMATH Keywords: matrix partitions
zbMATH Keywords: forbidden subgraphs
zbMATH Keywords: generalized colourings
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540836