Autores

4744
Diana Sasaki de Souza Pereira
2097,257,427
4745
2097,257,427
4746
2097,257,427

Informações:

Publicações do PESC

Título
Coloração Total de Famílias de Snarks
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
23/2/2010
Resumo

Uma colorao de arestas de um grafo G uma atribuio de cores s arestas do grafo de modo que duas arestas adjacentes no possuam a mesma cor. Uma colorao total de um grafo G uma colorao das arestas e dos vrtices de G tal que no existam dois elementos adjacentes com a mesma cor. O nmero cromtico total χT(G) o menor nmero de cores para o qual G admite uma colorao total.

Snarks so grafos simples, cbicos, sem ponte, que no so 3-aresta colorveis.

Este trabalho foi motivado pelo problema proposto por Cavicchioli et al [15] de determinar, caso exista, um snark com o menor nmero de vrtices tal que χT(G) = Δ+2. Nesta dissertao determinamos que χT(G) = Δ + 1 para a famlia de Snarks de Loupekhine, Blanusa famlias 1 e 2, e para as famlias que construmos com o produto interno, operao entre snarks introduzida por Isaacs [26]. Alm disso, estudamos propriedades do produto interno com relao colorao total.

Abstract

An edge coloring of a graph is an assignment of colors to the
edges of the graph so that no two adjacent edges have the same
color. A total coloring of a graph G is a coloring of the edges and the vertices of G such that no two adjacent elements have the same color. The total chromatic number χT(G) is the least number of colors required for a total coloring of G.

Snarks are simple connected bridgeless cubic graphs which are not 3-edge colorable.

This work was motivated by the problem proposed by Cavicchioli et al [15] of determining whether there exists a snark with the smallest number of vertices for which χT(G)= Δ+2. We determined that χT(G)= Δ+1 for the family of Loupekhine snarks, Blanusa First and Second, and for families that we construct using the dot product, operation between snarks introduced by Isaacs [26]. Moreover, we studied the dot product operation with respect to total coloring.

Topo