Aspectos da complexidade parametrizada para problemas de coloração de vértices em grafos com listas limitadas

A lista coloração é uma variação da coloração clássica de vértices em grafos muito estudada nos últimos anos. Foi introduzida por Erdos et al. em 1979. A lista coloração também possui algumas variações, dentre elas a (γ, μ)-coloração. Neste trabalho, esta elegante variação da lista coloração é considerada, onde mostramos que a (γ, μ)-coloração é W[1]-Difícil quando parametrizada pela largura arbórea do grafo de entrada, mesmo restrita a grafos bipartidos, porém é solucionável em tempo polinomial em grafos bipartidos quando γ< μ, isto é, quando listas unitárias não são permitidas. Além disso, um algoritmo FPT parametrizado pelo número da cobertura de vértices e pelo tamanho máximo da sua lista de cores é apresentado.