LIMITES PARA A SUBFALL-COLORAÇÃO DE GRAFOS LINHA

Resumo

Um grafo é um par de conjuntos finitos G=(V, E), sendo V o conjunto de vértices de G e E uma família de subconjuntos de dois elementos de V, chamados de arestas; são também denotados por V(G) e E(G). Um grafo H é dito subgrafo de G se o seu conjunto de vértices V(H) é um subconjunto de V(G) e se todas suas arestas pertencerem ao conjunto E(G). Um subgrafo induzido H de G é um subgrafo cujo conjunto de arestas E(H) contém um par {u,v} se e somente se u e v estão em V(H) e {u,v} está em E(G). Um problema muito investigado em Teoria dos Grafos é o problema de coloração, tendo em vista a sua utilidade em identificar relações em um conjunto e otimizar as mesmas. Uma k-coloração de G é uma função f: V(G) -> {1, 2, ..., k} que associa a cada vértice de G um valor, chamado de cor. Além disso, uma k-coloração é dita própria quando, para todo par {u,v} pertencente a E(G), f(u) é diferente de f(v). Ademais, um vértice v de G é chamado de b-vértice de f quando v é vizinho de pelo menos um vértice de cada cor diferente da sua. Uma k-Fall-Coloração de G é uma k-coloração própria tal que todo vértice de G é também b-vértice. Por outro lado, uma k-Subfall-Coloração de G é uma k-Fall-Coloração de algum subgrafo H de G. Neste trabalho, para ampliar o estudo da maximização de k-Subfall-Coloração, realizou-se um levantamento bibliográfico dos resultados existentes sobre k-Fall-Coloração e colorações associadas em certas classes de grafos e, após tal levantamento, decidiu-se investigar o caso particular de grafos linha. Até então, obtivemos limites tanto para grafos linha gerais quanto para grafos linha de grafos planares.