Coloração Total de Famílias de Snarks
Autores
|
4744 |
Diana Sasaki de Souza Pereira
|
2097,257,427
|
|
4745 |
2097,257,427
|
|
|
4746 |
2097,257,427
|
Informações:
Publicações do PESC
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.
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.