Improved bounds on coloring of graphs

Abstract

Given a graph $G$ with maximum degree $\Delta \ge 3$, we prove that the acyclic edge chromatic number $a^{\prime }(G)$ of $G$ is such that $a^{\prime }(G)\le \lceil 9.62(\Delta -1)\rceil$. Moreover we prove that: $a^{\prime }(G)\le \lceil 6.42(\Delta -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 ${\chi }_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}.

Introduction revised. Added references. Corrected typos. Proof of Theorem 2 (items c-f) written in more details

References in corpus (3)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• An Improvement of the Lovász Local Lemma via Cluster Expansion
• Properly coloured copies and rainbow copies of large graphs with small maximum degree