Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos

Abstract

In this work, the list coloring problem and choosability property in graphs are investigated. List coloring is a generalization of the vertex coloring problem in graph, and as this classic problem is to color a simple graph so that adjacent vertices have different colors, but respecting the additional constraint thaht each vertex has a list of porrible colors to be used. This problem has some variations as the (g;μ)-coloring, which involves sequential lists with lower and upper bounds known. The k-choosability is to determine the smallest size list k for which there is always a valid list coloring, whatever the distribution of the list in the graph. Thus, we investigated the correlation between k-choosability and (g;μ)-coloring, porposing the k-(g;μ)-choosability property. With this, we also analysed some proof tecnhiques in choosability, applied to determine k-(g;μ)-choosability for specific graphs are 3-(g;μ)-choosable and the technique of Marshal Hall, applied to prove that complete bipartite graphs are 2-(g;μ)-choosable. The most general result, obtaines throught a relatively simple formal proof, consisted to determine if a graph is k-colorable, then this graph is algo k-(g;μ)-choosable, leaving to be Pp 2-complete for NP-complete. Additionally, it was studied and implemented some algorithms to determine the list coloration and k-choosability for simple general graphs.