Paper detail

Improved bounds on coloring of graphs

Given a graph $G$ with maximum degree $Δ\ge 3$, we prove that the acyclic edge chromatic number $a'(G)$ of $G$ is such that $a'(G)\le\lceil 9.62 (Δ-1)\rceil$. Moreover we prove that: $a'(G)\le \lceil 6.42(Δ-1)\rceil$ if $G$ has girth $g\ge 5\,$; $a'(G)\le \lceil5.77 (Δ-1)\rc$ if $G$ has girth $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 \lc 6.59 Δ^{4/3}+3.3\D\rc$. We also prove that the star-chromatic number $χ_s(G)$ of $G$ is such that $χ_s(G)\le \lc4.34Δ^{3/2}+ 1.5\D\rc$. We finally prove that the $\b$-frugal chromatic number $χ^\b(G)$ of $G$ is such that $χ^\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 $\b$ such that $k_1(\b)\in[4, 6]$ and $k_2(\b)\in[2,5]$. To obtain these results we use an improved version of the Lovász Local Lemma due to Bissacot, Fernández, Procacci and Scoppola \cite{BFPS}.