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 coloração de arestas de um grafo G  é uma atribuição de cores às arestas do grafo de modo que duas arestas adjacentes não possuam a mesma cor. Uma coloração total de um grafo G é uma coloração das arestas e dos vértices de G tal que não existam dois elementos adjacentes com a mesma cor. O número cromático total χT(G) é o menor número de cores para o qual G admite uma coloração total.

 Snarks são grafos simples, cúbicos, sem ponte, que não são 3-aresta coloríveis.

Este trabalho foi motivado pelo problema proposto por Cavicchioli et al [15] de determinar, caso exista, um snark com o menor número de vértices tal que χT(G) = Δ+2. Nesta dissertação determinamos que χT(G) = Δ + 1 para a família de Snarks de Loupekhine, Blanusa famílias 1 e 2, e para as famílias que construímos com o produto interno, operação entre snarks introduzida por Isaacs [26]. Além disso, estudamos propriedades do produto interno com relação à coloração 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