Please use this identifier to cite or link to this item:
https://rd.uffs.edu.br/handle/prefix/2550
Type: | Tese |
Title: | Novel procedures for graph edge-colouring |
Author: | Zatesko, Leandro Miranda |
First advisor: | Carmo, Renato |
metadata.dc.contributor.advisor-co1: | Guedes, André Luiz Pires |
Resume: | O índice cromático de um grafo G é o menor número de cores necessário para colorir as arestas de G de modo que não haja duas arestas adjacentes recebendo a mesma cor. Pelo célebre Teorema de Vizing, o índice cromático de qualquer grafo simples G ou é seu grau máximo ∆, ou é ∆ +1, em cujo caso G é dito Classe 1 ou Classe 2, respectivamente. Computar uma coloração de arestas ótima de um grafo ou simplesmente determinar seu índice cromático são problemas NP-difíceis importantes que aparecem em aplicações notáveis, como redes de sensores, redes ópticas, controle de produção, e jogos. Neste trabalho, nós apresentamos novos procedimentos de tempo polinomial para colorir otimamente as arestas de grafos pertences a alguns conjuntos grandes. Por exemplo, seja X a classe dos grafos cujos maiorais (vértices de grau ∆) possuem soma local de graus no máximo ∆2−∆ (entendemos por ‘soma local de graus’ de um vértice x a soma dos graus dos vizinhos de x). Nós mostramos que quase todo grafo está em X e, estendendo o procedimento de recoloração que Vizing usou na prova para seu teorema, mostramos que todo grafo em X é Classe 1. Nós também conseguimos resultados em outras classes de grafos, como os grafos-junção, os grafos arco-circulares, e os prismas complementares. Como um exemplo, nós mostramos que um prisma complementar só pode ser Classe2 se for um grafo regular distinto do K2. No que diz respeito aos grafos-junção, nós mostramos que se G1 e G2 são grafos disjuntos tais que|V(G1)|6|V(G2)|e ∆(G1) > ∆(G2), e se os maiorais de G1 induzem um grafo acíclico, então o grafo-junção G1∗G2 é Classe1. Além desses resultados em coloração de arestas, apresentamos resultados parciais em coloração total de grafos-junção, de grafos arco-circulares, e de grafos cobipartidos, bem como discutimos um procedimento de recoloração para coloração total. |
Abstract: | The chromatic index of a graph G is the minimum number of colours needed to colour the edges of G in a manner that no two adjacent edges receive the same colour. By the celebrated Vizing’s Theorem, the chromatic index of any simple graph G is either its maximum degree ∆ or it is ∆+1, in which case G is said to be Class 1 or Class 2, respectively. Computing an optimal edge-colouring of a graph or simply determining its chromatic index are importantNP-hard problems which appear in noteworthy applications, like sensor networks, optical networks, production control, and games. In this work we present novel polynomial-time procedures for optimally edge-colouring graphs belonging to some large sets of graphs. For example, let X be the class of the graphs whose majors (vertices of degree ∆) have local degree sum at most ∆2−∆ (by ‘local degree sum’ of a vertex x we mean the sum of the degrees of the neighbours of x). We show that almost every graph is in X and, by extending the recolouring procedure used by Vizing’s in the proof for his theorem, we show that every graph in X is Class 1. We further achieve results in other graph classes, such as join graphs, circular-arc graphs, and complementary prisms. For instance, we show that a complementary prism can be Class 2 only if it is a regular graph distinct from the K2. Concerning join graphs, we show that if G1 and G2 are disjoint graphs such that |V(G1)|6|V(G2)|and ∆(G1) > ∆(G2), and if the majors of G1 induce an acyclic graph, thenthejoingraphG1∗G2 isClass1. Besidestheseresultsonedge-colouring,we present partial results on total colouring joingraphs,cobipartitegraphs,andcircular-arcgraphs, as well as a discussion on a recolouring procedure for total colouring. |
Keywords: | Teoria dos grafos Algoritmos e estrutura de dados |
Language: | eng |
Country: | Brasil |
Publisher: | Universidade Federal do Paraná |
Acronym of the institution: | UFPR |
Type of Access: | Acesso Aberto |
URI: | https://rd.uffs.edu.br/handle/prefix/2550 |
Issue Date: | 2018 |
metadata.dc.level: | Doutorado |
Appears in Collections: | Ciência da Computação Ciência da Computação |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ZATESKO.pdf | 4.18 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.