COLORAÇÃO DE GRUNDY PARCIAL EM SUBCLASSE DE COGRAFOS

XXXVII Encontro de Iniciação Científica

Felipe Cunha Falcao, Claudia Linhares Sales

Um grafo G = (V, E) é formado por um conjunto V de vértices e um conjunto E de arestas definidas por pares de vértices de G. Dois vértices são vizinhos se existe uma aresta que os une. Um caminho Pn é uma sequência de n vértices sem repetição na qual vértices sucessivos são vizinhos. Um grafo G&#039; = (V&#039;, E&#039;) é subgrafo induzido de G se V’ está contido em V e E’ é formado a partir de E retirando-se as arestas cujos vértices não estão em V’. Uma k-coloração própria de um grafo é uma rotulação de seus vértices com k rótulos para a qual não há vértices vizinhos de mesma cor. O número cromático de um grafo é o menor número natural tal que o grafo possui uma coloração própria. Dado um grafo colorido propriamente, um vértice de cor i é um vértice de Grundy se ele possui vizinhos com as cores 1, 2, ..., i - 1. Uma k-coloração gulosa parcial de um grafo é uma coloração própria na qual existe pelo menos um vértice de Grundy de cada uma das k cores. O número de Grundy parcial é o maior número natural k para o qual o grafo possui uma k-coloração gulosa parcial. Este texto é uma análise das relação entre a coloração gulosa parcial e o número cromático em uma classe específica de grafos: os grafos que não contém P4 (conhecidos como cografos), nem P3 U P2 como subgrafos induzidos. Para essa classe de grafos, provamos que se um grafo G pertence a essa classe, o número de Grundy parcial e o número cromático são iguais para todo subgrafo induzido de G.

Palavras-chave: Grafo. Coloração. Coloração Gulosa. Grundy.

Encontros Universitários da UFC, Fortaleza, v. 3, 2018

1132