Coloração acíclica

Abstract

We will present the state of the art for a sub-area of ​​coloration in graphs known as acyclic coloration. Given a G fi nite graph, we have an acyclic k-coloration of G when we have a proper k-coloration for G such that any two color classes induce in G a vector, that is, an acyclic subgraph. The smallest positive integer k such that G admits an acyclic k-coloration is the acyclic chromatic number of G, denoted by χa (G). We believe that this is the first text to summarize the state of the art for this problem, even considering other languages. We present the results organized by type. First, we present those related to the limitation for the acyclic chromatic number, referring to the cyclic coloration in vertices, in edges and acyclic coloration by lists in vertices and edges. Next, we list the results concerning the computational complexity of the problem of determining if it is possible to acyclically colorize a graph G with k colors, given a graph G and a positive integer k. Finally, we present open questions for future research.