Minimal digraph obstructions for small matrices

2016/05/31 by Hell, Pavol, Hernández-Cruz, César
#05C15 #05C20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1605.09587

Abstract

Given a \ 0, 1, ∗ \-matrix M, a minimal M-obstruction is a digraph D such that D is not M-partitionable, but every proper induced subdigraph of D is. In this note we present a list of all the M-obstructions for every 2 × 2 matrix M. Notice that this note will be part of a larger paper, but we are archiving it now so we can cite the results.

Related

• Point determining digraphs, \0,1\-matrix partitions, and dualities in full homomorphisms
• Minimal obstructions for a matrix partition problem in chordal graphs
• Almost all friendly matrices have many obstructions
• Matrix Partitions of Split Graphs
• Obstructions for linear rankwidth at most 1