pith. sign in

arxiv: 1905.12484 · v1 · pith:GZBUJ5NTnew · submitted 2019-05-29 · 💻 cs.DM · math.CO

Oriented coloring of graphs with low maximum degree

classification 💻 cs.DM math.CO
keywords orienteddegreegraphsmaximumrespchromaticnumberbound
0
0 comments X
read the original abstract

Duffy et al. [C. Duffy, G. MacGillivray, and \'E. Sopena, Oriented colourings of graphs with maximum degree three and four, Discrete Mathematics, 342(4), p. 959--974, 2019] recently considered the oriented chromatic number of connected oriented graphs with maximum degree $3$ and $4$, proving it is at most $9$ and $69$, respectively. In this paper, we improve these results by showing that the oriented chromatic number of non-necessarily connected oriented graphs with maximum degree $3$ (resp. $4$) is at most $9$ (resp. $26$). The bound of $26$ actually follows from a general result which determines properties of a target graph to be universal for graphs of bounded maximum degree. This generalization also allows us to get the upper bound of $90$ (resp. $306$, $1322$) for the oriented chromatic number of graphs with maximum degree $5$ (resp. $6$, $7$).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.