Improved bounds on coloring of graphs

Given a graph G with maximum degree Delta >= 3, we prove that the acyclic edge chromatic number a' (G) of G is such that a'(G) <= [9.62(Delta - 1)]. Moreover we prove that: a' (G) <= [6.42(Delta - 1)] if G has girth g >= 5; a' (G) <= [5.7(Delta - 1)] if G has girth g >= 7; a' (G) <= [4.52(Delta - 1)] if g >= 53; a' (G) <= Delta + 2 if g >= [25.84 Delta log Delta(1 + 4.1/log Delta]. We further prove that the acyclic (vertex) chromatic number a(G) of G is such that a(G) <= [6.59 Delta(4/3) + 3.3 Delta]. We also prove that the star-chromatic number chi(s)(G) of G is such that chi(s)(G) <= [4.34 Delta(3/2) + 1.5 Delta]. We finally prove that the beta-frugal chromatic number chi(beta)(G) of G is such that chi(beta)(G) <= [max{k(1)(similar to beta)Delta, k(2)(beta)Delta(1+1 beta)/(beta!)(1/beta)}]. where k(1)(beta) and k(2)(beta) are decreasing functions of beta such that k(1)(beta) is an element of [4,6] and k(2)(beta) is an element of [2, 5]. To obtain these results we use an improved version of the Lovasz Local Lemma due to Bissacot et al. (2011) [6]. (C) 2011 Elsevier Ltd. All rights reserved.