z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here