Coloração de Grafos k-Coloráveis Aleatórios e Semi-Aleatórios

O problema de colorir um grafo com o menor número de cores é bem conhecido por ser NP-difícil, mesmo restrito a grafos k-coloráveis para k constante ≥ 3. Por outro lado, é sabido que grafos k-coloráveis aleatórios são fáceis de k-colorir. No entanto, os algoritmos para colorir grafos k-coloráveis aleatórios requerem densidades de arestas bastante altas. Neste artigo, apresentamos algoritmos que coloram grafos k-coloráveis gerados aleatoriamente para densidades de arestas muito mais baixas do que abordagens anteriores. Além disso, para estudar uma variedade mais ampla de distribuições de grafos, também apresentamos um modelo de grafos gerados pela fonte semi-aleatória de Santha e Vazirani (M. Santha e U. V. Vazirani, J. Comput. System Sci.33 (1986), 75-87) que proporciona uma transição suave entre os modelos de pior caso e aleatórios. Neste modelo, o grafo é gerado por um "adversário ruidoso" - um adversário cujas decisões (se deve ou não inserir uma aresta particular) têm alguma pequena probabilidade (aleatória) de serem revertidas. Mostramos que mesmo para taxas de ruído bastante baixas, grafos k-coloráveis semi-aleatórios podem ser otimizados com alta probabilidade.