Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/25776| Título: | Coloração de arestas em grafos split-comparabilidade e split-intervalos |
| Título(s) alternativo(s): | Edge coloring in split-comparability and split-interval graphs |
| Autor(es): | Gonzaga, Luis Gustavo da Soledade |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Representações dos grafos Teoria dos grafos Cores Algorítmos computacionais Representations of graphs Graph theory Colors Computer algorithms |
| Data do documento: | 20-Abr-2021 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | GONZAGA, Luis Gustavo da Soledade. Coloração de arestas em grafos split-comparabilidade e split-intervalos. 2021. Dissertação (Mestrado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2021. |
| Resumo: | Uma coloração de arestas própria de um grafo é uma atribuição de cores para as suas arestas tal que arestas incidentes em um mesmo vértice têm cores distintas. O Problema da Coloração de Arestas é responder, dado um grafo, qual o menor número de cores para uma coloração de arestas própria. Esse número é chamado de índice cromático e, para um grafo 𝐺, é denotado por 𝜒′(𝐺). Por definição, o índice cromático é pelo menos ∆(𝐺), onde ∆(𝐺) é o maior número de arestas incidentes em um mesmo vértice do grafo 𝐺. Em 1964, Vizing provou que 𝜒′(𝐺) ≤ ∆(𝐺) + 1 para qualquer grafo simples 𝐺. Portanto, quando 𝐺 é simples, ∆(𝐺) ≤ 𝜒′(𝐺) ≤ ∆(𝐺) + 1. Um grafo é Classe 1 se o seu índice cromático é igual ao seu grau máximo, e é Classe 2 caso contrário. O Problema da Classificação é decidir se um grafo simples é Classe 1. A despeito de haver apenas dois possíveis valores para o índice cromático de um grafo simples, o Problema da Classificação é NP-completo. Em 1985, em sua famosa coluna "The NP-Completeness Column: an Ongoing Guide”, David Johnson classificou alguns problemas da Teoria dos Grafos em relação à sua complexidade computacional. Em alguns casos, esta complexidade ainda era desconhecida e Johnson identificou classes de grafos para as quais considerou que seria fácil determiná-la. Nas classes de grafos split, de comparabilidade e de intervalos, por exemplo, Johnson considerou que determinar a complexidade computacional do Problema da Classificação era possivelmente fácil. Entretanto, após 35 anos, apenas a complexidade computacional do Problema da Classificação para os grafos de comparabilidade foi determinada, sendo este um problema NP-completo. Esta dissertação apresenta uma solução de tempo polinomial para o Problema da Classificação para grafos split-intervalos, além de identificar e corrigir um problema na prova que determina o índice cromático dos grafos split-comparabilidade. |
| Abstract: | A proper edge coloring of a graph is an assignment of colors to its edges such that edges incident with the same vertex have distinct colors. The Edge Coloring Problem is answering, given a graph, which is the least number of colors for a proper edge coloring. That number is called the chromatic index and, for a graph 𝐺, it is denoted 𝜒′ (𝐺). By definition, the chromatic index is at least ∆(𝐺), wherein ∆(𝐺) is the largest number of edges incident with the same vertex of the graph 𝐺. In 1964, Vizing proved that 𝜒′(𝐺) ≤ ∆(𝐺) + 1 for every simple graph 𝐺. Therefore, when 𝐺 is a simple graph, ∆(𝐺) ≤ 𝜒′(𝐺) ≤ ∆(𝐺)+1. A graph is Class 1 if its chromatic index equals its maximum degree, and it is Class 2 otherwise. The Graph Classification Problem is deciding if a simple graph is Class 1. Even considering that there are only two possible values for the chromatic index, the Graph Classification Problem is still NP-complete. In 1985, in his famous column "The NP-Completeness Column: an Ongoing Guide”, David Johnson classified some problems in Graph Theory concerning their computational complexity. In some cases, that complexity was still unknown and Johnson identified graph classes for which he considered it would be easier to determine it. On the classes of split, comparability, and intervals graphs, for instance, Johnson considered that determining the computational complexity of the Classification Problem was possibly easy. However, after 35 years, only the computational complexity of the Classification Problem for comparability graphs was determined, being it an NP-complete problem. This thesis presents a polynomial-time solution for the Classification Problem for splitinterval graphs, besides identifying and correcting an issue in the previous proof that determined the chromatic index of split-comparablility graphs. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/25776 |
| Aparece nas coleções: | PG - Programa de Pós-Graduação em Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracaoarestagrafossplit.pdf | 1,35 MB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
