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$). |
Year | Venue | DocType |
---|---|---|
2019 | arXiv: Discrete Mathematics | Journal |
Volume | Citations | PageRank |
abs/1905.12484 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pascal Ochem | 1 | 258 | 36.91 |
Alexandre Pinlou | 2 | 167 | 20.47 |