Acyclic colorings of graphs and the probabilistic method
Time: 14:00 -- Location: LRI, 445
summary: Graph colorings have been extensively studied for the past century, due to the richness of the theory and its numerous applications. Part of the current research focuses on constrained colorings, and how their properties differ from proper colorings. When we require that, in a proper coloring, no (even) cycle is 2-colored, we obtain what is called an acyclic coloring. This goal aims at exploring the various properties of such colorings. We are especially interested in the asymptotic behaviour of vertex acyclic colorings, and try to give the best possible bounds in terms of the maximum degree Δ. In the same manner that a graph can be greedily colored using at most Δ+1 colors, it is possible to greedily construct an acyclic coloring using at most Δ²+1 colors. It turns out that this greedy bound for acyclic coloring is far from optimal. In fact, breakthroughs in this domain have only been achieved by using probabilistic tools. We will first review the state of the art, giving some insight into the techniques used. We will then take a look at the properties of acyclic colorings when we forbid some cycle lengths in the graph.