Número cromático acíclico das arestas de um grafo com girth grande

Abstract

This work aims to enrich the study of acyclic edge coloring of a graph G = (V,E), with a minimum girth g, based on Moser-Tardos type random algorithms. Let ∆ be the maximum degree of a vertex v in a graph G. The acyclic chromatic index of G, denoted by a ′(G), is the smallest number of colors required to properly color its edges such that none of its cycles are bichromatic. It was conjectured by Fiamˇcik [14] and after for [2] that a ′ (G) ≤ ∆ + 2. Over time, researchers have sought a better upper bound for a ′ (G). Currently, the best result is by Fialho, Lima, and Procacci [13], who established that a ′ (G) ≤ 3.569(∆−1). In this work, for any ε > 0, we explicitly determine a girth g(ε,m), where m is the number of edges, such that if g ≥ g(ε,m), then G admits an acyclic edge coloring with (1 + ε)∆ colors. Moreover, the Main Theorem presented later in the Introduction, demonstrates that by fixing the number of edges m, Fiamˇcik’s conjecture holds for g ≥ g∆,m. For example, by fixing m = 5 × 105 and for g ≥ 35, the conjecture is valid.