Improved bounds on coloring of graphs

Given a graph GG with maximum degree Δ≥3Δ≥3, we prove that the acyclic edge chromatic number a′(G)a′(G) of GG is such that a′(G)≤⌈9.62(Δ−1)⌉a′(G)≤⌈9.62(Δ−1)⌉. Moreover we prove that: a′(G)≤⌈6.42(Δ−1)⌉a′(G)≤⌈6.42(Δ−1)⌉ if GG has girth g≥5; a′(G)≤⌈5.77(Δ−1)⌉a′(G)≤⌈5.77(Δ−1)⌉ if GG has girth g≥7g≥7; a′(G)≤⌈4.52(Δ−1)⌉a′(G)≤⌈4.52(Δ−1)⌉ if g≥53g≥53; a′(G)≤Δ+2a′(G)≤Δ+2 if g≥⌈25.84ΔlogΔ(1+4.1/logΔ)⌉g≥⌈25.84ΔlogΔ(1+4.1/logΔ)⌉. We further prove that the acyclic (vertex) chromatic number a(G)a(G) of GG is such that a(G)≤⌈6.59Δ4/3+3.3Δ⌉a(G)≤⌈6.59Δ4/3+3.3Δ⌉. We also prove that the star-chromatic number χs(G)χs(G) of GG is such that χs(G)≤⌈4.34Δ3/2+1.5Δ⌉χs(G)≤⌈4.34Δ3/2+1.5Δ⌉. We finally prove that the ββ-frugal chromatic number χβ(G)χβ(G) of GG is such that χβ(G)≤⌈max{k1(β)Δ,k2(β)Δ1+1/β/(β!)1/β}⌉χβ(G)≤⌈max{k1(β)Δ,k2(β)Δ1+1/β/(β!)1/β}⌉, where k1(β)k1(β) and k2(β)k2(β) are decreasing functions of ββ such that k1(β)∈[4,6]k1(β)∈[4,6] and k2(β)∈[2,5]k2(β)∈[2,5]. To obtain these results we use an improved version of the Lovász Local Lemma due to Bissacot et al. (2011) [6].