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.77(Delta − 1)⌉ if G has girth g ≥ 7; a′(G) ≤ ⌈4.52(Delta − 1)⌉ if g ≥ 53; a′(G) ≤ Delta + 2 if g ≥ ⌈25.84Delta logDelta (1 + 4.1/ logDelta)⌉. We further prove that the acyclic (vertex) chromatic number a(G) of G is such that a(G) ≤ ⌈6.59Delta4/3+ 3.3Delta⌉. We also prove that the star-chromatic number chi s(G) of G is such that chi s(G) ≤ ⌈4.34Delta3/2 +1.5Delta⌉. We finally prove that the beta-frugal chromatic number chi beta(G) of G is such that chi beta(G) ≤ ⌈max{k1(beta)Delta, k2(beta)Delta^1+1/beta/(beta!)^1/beta}⌉, where k1(beta) and k2(beta) are decreasing functions of beta such that k1(beta) ∈ [4, 6] and k2(beta) ∈ [2, 5]. To obtain these results we use an improved version of the Lov´asz Local Lemma due to Bissacot, Fern´andez, Procacci and Scoppola [6].