We also obtain a relationship connecting the oriented chromatic number of graphs and the -subgraph chromatic numbers introduced and studied in Aravind and Subramanian (2011) . In particular, we relate the oriented chromatic number and the -treewidth chromatic number and show that for any graph having -treewidth chromatic number at most . The latter parameter is the least number of colors in any proper vertex coloring which is such that the subgraph induced by the union of any two color classes has treewidth at most?.
We also generalize a result of Alon et?al. (1996) on acyclic chromatic number of graphs on surfaces (with characteristic ) to -subgraph chromatic numbers and prove that for some constant depending only on . We also show that this bound is nearly tight. We then use this result to show that graphs of genus have oriented chromatic number at most for every fixed . We also refine the proof of a bound on obtained by Kostochka et?al. (1997) in? to obtain an improved bound on .