Improved bounds on coloring of graphs

Given a graph $G$ with maximum degree $\mathrm{\Delta }\ge 3$, we prove that the acyclic edge chromatic number $a^{\mathrm{\prime }}(G)$ of $G$ is such that $a’(G)\le\lceil 9.62 (\Delta-1)\rceil$\mathrm{.}Moreoverweprovethat:$a’(G)\le \lceil 6.42(\Delta-1)\rceil$if$G$hasgirth$g\ge 5,$;$a’(G)\le \lceil5.77 (\Delta-1)\rc$if$G$hasgirth$g\ge 7$;$a’(G)\le \lc4.52(\D-1)\rc$if$g\ge 53$;$a’(G)\le \D+2,$if$g\ge \lceil25.84\D\log\D(1+ 4.1/\log\D)\rceil$. We further prove that the acyclic (vertex) chromatic number $a(G)$ of $G$ is such that $a(G)\le \text{lc}6.59{\mathrm{\Delta }}^{4\mathrm{/}3}+3.3\text{D}\text{rc}$. We also prove that the star-chromatic number ${\chi }_s(G)$ of $G$ is such that $\chi_s(G)\le \lc4.34\Delta^{3/2}+ 1.5\D\rc$\mathrm{.}Wefinallyprovethatthe$\b$-frugal chromatic number ${\chi }^{\text{b}}(G)$ of $G$ is such that $\chi^\b(G)\le \lc\max{k_1(\b)\D,; k_2(\b){\D^{1+1/\b}/ (\b!)^{1/\b}}}\rc$,where$k_1(\b)$and$k_2(\b)$ are decreasing functions of $\text{b}$ such that $k_1(\text{b})\in [4,6]$ and $k_2(\text{b})\in [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 \cite{BFPS}.