Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275545
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Coloração de arestas semiforte de grafos split
Title Alternative: Adjacent strong edge-coloring of split graphs
Author: Vilas-Bôas, Aloísio de Menezes, 1987-
Advisor: Mello, Célia Picinin de, 1950-
Abstract: Resumo: Seja G um grafo simples. Uma coloração de arestas semiforte de G é uma coloração de arestas de G onde para cada par de vértices adjacentes u,v de G, o conjunto das cores atribuídas às arestas de u é diferente do conjunto das cores atribuídas às arestas de v. O índice cromático semiforte de G, denotado por chi'a(G), é o menor número de cores necessário para construir uma coloração de arestas semiforte para G. Esta coloração foi proposta por Zhang et al. em 2002. Nesse mesmo artigo, os autores conjecturaram que todo grafo simples conexo G, G diferente de C_5, com pelo menos três vértices possui chi'a(G) menor ou igual a Delta(G)+2. Esta conjectura conhecida como conjectura da coloração de arestas semiforte está aberta para grafos arbitrários, mas é válida para algumas classes de grafos. Nesta dissertação, apresentamos alguns resultados sobre a coloração de arestas semiforte. Em seguida, focamos em grafos split. Provamos a conjectura da coloração de arestas semiforte para algumas famílias destes grafos, dentre elas, os split-completos e os split-indiferença. Além disso, determinamos o índice cromático semiforte dos grafos split-indiferença com vértice universal. Para grafos split-indiferença sem vértice universal, exibimos condições para que seu índice cromático semiforte seja igual a Delta(G)+1 e conjecturamos chi'a(G) = Delta(G)+2 caso contrário

Abstract: Let G be a simple graph. An adjacent strong edge-coloring of G is an edge-coloring of G such that for each pair of adjacent vertices u,v of G, the set of colors assigned to the edges incident with u differs from the set of colors assigned to the edges incident with v. The adjacent strong chromatic index, denoted chi'a(G), of G is the minimum number of colors required to produce an adjacent strong edge-coloring for G. This coloring was proposed by Z. Zhang et al. In the same article, the authors conjectured that every simple connected graph G with at least three vertices and G not equal to C_5 (a 5-cycle) has chi'a(G) less or equal then Delta(G)+2. This conjecture is open for arbitrary graphs, but it holds for some classes of graphs. In this dissertation, we present some results on adjacent strong edge-coloring. Then, we focus on split graphs. We prove the conjecture for some families of split graphs including split-complete graphs and split-indifference graphs. Moreover, we determine a necessary condition for split-complete graphs G to have chi'a(G) = Delta(G)+1 and we determine the adjacent strong chromatic index for split-indifference graphs with a universal vertex. For a split-indifference graph G without universal vertices, we give conditions for its adjacent strong chromatic index to be Delta(G)+1 and we conjecture that chi'a(G) = Delta(G)+2, otherwise
Subject: Teoria dos grafos
Coloração de grafos
Editor: [s.n.]
Date Issue: 2015
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Vilas-Boas_AloisiodeMenezes_M.pdf3 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.