Premium
On unavoidable digraphs in orientations of graphs
Author(s) -
Bloom Gary S.,
Burr Stefan A.
Publication year - 1987
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.3190110402
Subject(s) - combinatorics , mathematics , chromatic scale , homomorphism , tournament , graph , discrete mathematics , graph homomorphism , transitive relation , critical graph , graph power , line graph
Let G be a graph, and let D be a directed graph. Write G → D to mean that, no matter how the edges of G are given orientations, a copy of D must appear as a subgraph of the resulting oriented graph. It is proved that among all G for which G → D , the minimum chromatic number is equal to the minimum k for which K k → hom( D ), where hom( D ) is the set of homomorphs of D . Next, necessary and sufficient conditions are given for a directed graph to have a homomorphism into a given transitive tournament, directed path, or directed cycle. These results are then applied to various cases of the above theorem. In particular, the minimum chromatic number is evaluated whenever D is an oriented forest, and all D are characterized for which the minimum chromatic number is no more than three.