Premium
Acyclic and oriented chromatic numbers of graphs
Author(s) -
Kostochka A. V.,
Sopena E.,
Zhu X.
Publication year - 1997
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/(sici)1097-0118(199704)24:4<331::aid-jgt5>3.0.co;2-p
Subject(s) - combinatorics , mathematics , chromatic scale , homomorphism , upper and lower bounds , graph , friendship graph , discrete mathematics , windmill graph , critical graph , bound graph , graph power , line graph , mathematical analysis
The oriented chromatic number χ o (G → ) of an oriented graph G → = ( V, A ) is the minimum number of vertices in an oriented graph H → for which there exists a homomorphism of G → to H → . The oriented chromatic number χ o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the orientations of G . This paper discusses the relations between the oriented chromatic number and the acyclic chromatic number and some other parameters of a graph. We shall give a lower bound for χ o (G) in terms of χ a (G) . An upper bound for χ o (G) in terms of χ a (G) was given by Raspaud and Sopena. We also give an upper bound for χ o (G) in terms of the maximum degree of G . We shall show that this upper bound is not far from being optimal. © 1997 John Wiley & Sons, Inc.