@MASTERSTHESIS{ 2016:1943072169,
 	title = {Sobre problemas de lista coloração e a propriedade de selecionabilidade em grafos},
 	year = {2016},
 	url = "http://tede.ufam.edu.br/handle/tede/5650",
 	abstract = "Nesta dissertação, o problema da lista coloração e a propriedade da selecionabilidade
 em grafos são abordados. Lista coloração é uma generalização do problema da coloração
 de vértices em grafos, e tal como este problema clássico, consiste em colorir um grafo
 simples de modo que vértices adjacentes possuam cores distintas, mas, respeitando- se a
 restrição adicional de que cada vértice possui uma lista restrita de possíveis cores a serem
 usadas. Tal problema possui algumas variações, como a (g;μ)-coloração, que envolve listas
 sequenciais com limite inferior e superior conhecidos. A k-selecionabilidade consiste
 em determinar o menor tamanho de lista k para o qual sempre há uma lista coloração,
 seja qual for a distribuição de lista no grafo. Nesta dissertação, se investigou a correlação
 entre a propriedade da k-selecionabilidade e a (g;μ)-coloração, sendo definida a propriedade
 de k-(g;μ)-selecionabilidade. Com isto, foram também estudadas algumas técnicas
 de prova em selecionabilidade, aplicadas para se determinar a k-(g;μ)-selecionabilidade
 para classes específicas de grafos, como a técnica de degeneração em grafos, usada para
 provar que grafos periplanares são 3-(g;μ)-selecionáveis e a técnica de Marshal Hall,
 usada para provar que grafos bipartidos completos são 2-(g;μ)-selecionáveis. O resultado
 mais geral, obtido através de uma prova formal, consistiu em determinar que se um grafo é
 k-colorível, então tal grafo também é k-(g;μ)-selecionável, deixando de ser Pp
 2-completo
 para ser NP-completo. Adicionalmente, foram estudados e implementados alguns algoritmos
 para determinar a lista coloração e k-selecionabilidade em grafos simples gerais",
 	publisher = {Universidade Federal do Amazonas},
 	scholl = {Programa de Pós-graduação em Informática},
 	note = {Instituto de Computação}
}