Improved bounds on coloring of graphs

AbstractGiven a graph G with maximum degree Δ≥3, we prove that the acyclic edge chromatic number a′(G) of G is such that a′(G)≤⌈9.62(Δ−1)⌉. Moreover we prove that: a′(G)≤⌈6.42(Δ−1)⌉ if G has girth g≥5; a′(G)≤⌈5.77(Δ−1)⌉ if G has girth g≥7; a′(G)≤⌈4.52(Δ−1)⌉ if g≥53; a′(G)≤Δ+2 if g≥⌈25.84ΔlogΔ(1+4.1/logΔ)⌉. We further prove that the acyclic (vertex) chromatic number a(G) of G is such that a(G)≤⌈6.59Δ4/3+3.3Δ⌉. We also prove that the star-chromatic number χs(G) of G is such that χs(G)≤⌈4.34Δ3/2+1.5Δ⌉. We finally prove that the β-frugal chromatic number χβ(G) of G is such that χβ(G)≤⌈max{k1(β)Δ,k2(β)Δ1+1/β/(β!)1/β}⌉, where k1(β) and k2(β) are decreasing functions of β such that k1(β)∈[4,6] and 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]