Premium
On homomorphisms to acyclic local tournaments
Author(s) -
Hell Pavol,
Zhou Huishan,
Zhu Xuding
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200410
Subject(s) - tournament , digraph , homomorphism , combinatorics , mathematics , transitive relation , vertex (graph theory) , simple (philosophy) , directed graph , path (computing) , discrete mathematics , graph , computer science , philosophy , epistemology , programming language
A homomorphism of a digraph to another digraph is an edgepreserving vertex mapping. A local tournament is a digraph in which the inset as well as the outset of each vertex induces a tournament. Thus acyclic local tournaments generalize both directed paths and transitive tournaments. In both these cases there is a simple characterization of homomorphic preimages. Namely, if H is a directed path, or a transitive tournament, then G admits a homomorphism to H if and only if each oriented path which admits a homomorphism to G also admits a homomorphism to H . We prove that this result holds for all acyclic local tournaments. © 1995 John Wiley & Sons, Inc.