@MASTERSTHESIS{ 2016:384678093,
 	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}
}