Forbidden subgraph colorings and the oriented chromatic number

We present an improved upper bound of O(d1+1m−1) for the (2,F)(2,F)-subgraph chromatic number χ2,F(G)χ2,F(G) of any graph GG of maximum degree dd. Here, mm denotes the minimum number of edges in any member of FF. This bound is tight up to a (logd)1/(m−1)(logd)1/(m−1) multiplicative factor and improves the previous bound presented in Aravind and Subramanian (2011) [5]. Along the way, we state and prove an easy-to-use version of the Lovász Local Lemma.We also obtain a relationship connecting the oriented chromatic number χo(G)χo(G) of graphs and the (j,F)(j,F)-subgraph chromatic numbers χj,F(G)χj,F(G) introduced and studied in Aravind and Subramanian (2011) [5]. In particular, we relate the oriented chromatic number and the (2,r)(2,r)-treewidth chromatic number and show that χo(G)≤k((r+1)2r)k−1χo(G)≤k((r+1)2r)k−1 for any graph GG having (2,r)(2,r)-treewidth chromatic number at most kk. 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 rr.We also generalize a result of Alon et al. (1996) [3] on acyclic chromatic number of graphs on surfaces (with characteristic −γ≤0−γ≤0) to (2,F)(2,F)-subgraph chromatic numbers and prove that χ2,F(G)=O(γm/(2m−1))χ2,F(G)=O(γm/(2m−1)) for some constant mm depending only on FF. We also show that this bound is nearly tight. We then use this result to show that graphs of genus gg have oriented chromatic number at most 2O(g1/2+ϵ)2O(g1/2+ϵ) for every fixed ϵ>0ϵ>0. We also refine the proof of a bound on χo(G)χo(G) obtained by Kostochka et al. (1997) in [10] to obtain an improved bound on χo(G)χo(G).