Colorações de Grafos Arco-Circulares

O problema da coloração de vértices é um dos problemas clássicos em teoria dos grafos, possuindo aplicações na modelagem de diversos problemas. Em particular, o problema da coloração de vértices de grafos arco-circulares possui aplicações nas áreas de escalonamento de tarefas e otimização de compiladores. Este trabalho apresenta alguns dos principais resultados relativos ao problema da coloração de vértices, bem como novos resultados em duas variantes deste problema: coloração de cliques e λ-coloração, restrito a grafos arco-circulares. Para coloração de cliques é exibido um algoritmo polinomial, enquanto que para λ-coloração é apresentada uma análise dos trabalhos existentes na literatura e é provado que a conjectura do limite superior do quadrado do grau do grafo é verdadeira para grafos arco-circulares.