B-COLORAÇÃO DE GRAFOS COM CINTURA ALTA E PROBLEMAS RELACIONADOS.

Resumo

Dada uma coloração própria c de G, um vértice é dito de Grundy se é adjacente a pelo menos um vértice de cada uma das cores anteriores à sua. Uma coloração é parcial de Grundy se toda classe de cor contém pelo menos um vértice de Grundy. O número de Grundy parcial é o maior inteiro k para o qual G possui uma coloração de Grundy. Neste trabalho, atacamos a coloração parcial de Grundy de grafos com cintura ao menos 7, onde a cintura de um grafo é o tamanho do menor ciclo existente. Foi estudado o artigo "An algorithm for partial Grundy number on trees", que prova que encontra o número parcial de Grundy de grafos com cintura ao menos 9. De forma interessante, este resultado se assemelha a um resultado conhecido acerca de outro parâmetro de coloração em grafos, definido a seguir: Uma b-coloração de um grafo G é uma coloração própria dos vértices de G de forma que em cada classe de cor, existe ao menos um vértice que é adjacente a cada outra classe de cor; tal vértice é chamado de b-vértice. Dentre as propriedades existentes, há uma citada e provada no artigo "graphs of girth at least 7 have high b-chromatic number", da European Journal of Combinatorics, que tem como co-autora a orientadora desta bolsa. No artigo, o Teorema [13] afirma que: Se G tem cintura pelo menos 7 e possui um "good set", então b(G)=m(G). A motivação em estudar este artigo foi para adaptar e melhorar o teorema citado anteriormente, sobre coloração parcial de Grundy, na tentativa de baixar o tamanho da cintura de 9 para 7. Foi possível alcançar provas parciais desta proposição, adaptando-a em um dos lemas deste último artigo.