Point determining digraphs, \0,1\-matrix partitions, and dualities in full homomorphisms

2013/08/01 by Pavol Hell, Hell, Pavol, César Hernández-Cruz +1
Mathematics · #05C20 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20 #msc:05C69

paper · pdf · doi:10.48550/arxiv.1308.0377

12 pages

arxiv created 2013/08/01 · arxiv updated 2013/08/05

Abstract

We prove that every point-determining digraph D contains a vertex v such that D-v is also point determining. We apply this result to show that for any \0,1\-matrix M, with k diagonal zeros and ℓ diagonal ones, the size of a minimal M-obstruction is at most (k+1)(ℓ+1). This extends the results of Sumner, and of Feder and Hell, from undirected graphs and symmetric matrices to digraphs and general matrices.

Related

• Minimal digraph obstructions for small matrices
• Almost all friendly matrices have many obstructions
• Matrix Partitions of Split Graphs
• Minimal obstructions for a matrix partition problem in chordal graphs
• Bigraphs versus digraphs via matrices