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

DOI10.1016/J.DISC.2014.12.001MaRDI QIDQ2346339zbMATH OpenOpenAlexFDO

Authors César Hernández-Cruz, Pavol Hell

Publication date 1 June 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.0377

zbMATH Keywords

full homomorphismgeneralized colouringhomogeneous setmatrix partitionminimal obstructionpoint determining digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

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 $ell$ diagonal ones, the size of a minimal $M$-obstruction is at most $(k+1)(ell+1)$. This extends the results of Sumner, and of Feder and Hell, from undirected graphs and symmetric matrices to digraphs and general matrices.

Recommendations

• On realizations of point determining graphs, and obstructions to full homomorphisms
• Digraph matrix partitions and trigraph homomorphisms
• Publication:4729827
• scientific article; zbMATH DE number 90552
• \(\mathcal{B}\)-partitions, determinant and permanent of graphs
• Point partition numbers: decomposable and indecomposable critical graphs
• Duality for finite bipartite graphs (with an application to II\(_ 1\) factors)
• Edge partitions of the complete graph and a determinant-like function
• On the partition associated to the smallest eigenvalues of the k-point fixing graph
• Fixed points of posets and clique graphs

Cites work

• Dualities in full homomorphisms
• Graph partitions with prescribed patterns
• scientific article; zbMATH DE number 3650785 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• List Partitions
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Point determination in graphs

Cited in

(3)

• Gaps in full homomorphism order
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Full-homomorphisms to paths and cycles

This page was built for publication: Point determining digraphs, \(\{ 0,1 \}\)-matrix partitions, and dualities in full homomorphisms

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