Acyclic and Oriented Chromatic Numbers of Graphs

A. V. Kostochka, E. Sopena, X. Zhu

Research output: Contribution to journalArticlepeer-review

Abstract

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 χα(G). An upper bound for χo(G) in terms of χα(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.

Original languageEnglish (US)
Pages (from-to)331-340
Number of pages10
JournalJournal of Graph Theory
Volume24
Issue number4
DOIs
StatePublished - Apr 1997
Externally publishedYes

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Acyclic and Oriented Chromatic Numbers of Graphs'. Together they form a unique fingerprint.

Cite this