Por favor, use este identificador para citar o enlazar este ítem:
https://rd.uffs.edu.br/handle/prefix/1205| Type: | Monografia |
| Título : | Classificação de cografos quanto ao índice cromático |
| Author: | Lima, Alex Reimann Cunha |
| First advisor: | Zatesko, Leandro Miranda |
| Resume: | Coloração de arestas, um problema que consiste em descobrir quantas cores são necessárias para obter uma coloração mínima das arestas de um grafo, é NP-completo (ainda que só haja duas possibilidades para o número mínimo de cores, conforme o Teorema de Vizing). Contudo, quando se trata de algumas subclasses de grafos, já restou provado que o problema admite solução polinomial ou linear. No caso dos cografos (grafos que não possuem um P4 como subgrafo induzido), esse problema ainda não foi resolvido. Entretanto há indícios de que ele admita não apenas solução polinomial mas também linear, haja vista a existência da Conjectura Overfull e outros resultados relacionados à coloração de arestas de subclasses de cografos. A partir dessa constatação, é proposta uma conjectura, baseada em evidências extraídas de um programa especialmente projetado para a geração de cografos, acerca da operação de junção quando quando um deles possui núcleo acíclico. Além disso, são apresentados dois teoremas para casos mais restritos da conjectura: quando o núcleo acíclico não possuir arestas e quando houver um emparelhamento que não cubra o núcleo do outro grafo. |
| Resumen : | Edge colouring, a problem which consists in figuring out how many colours are needed to provide a minimal colouring of the edges of a graph, is NP-complete (even though, according to Vizing’s Theorem, there are only two possibilities for the minimum number of colours). However, when dealing with some graph subclasses, it admits a polynomial or linear solution. For cograph class (graphs which do not have a P4 as an induced subgraph), this problem has not been solved yet. Nevertheless there are indications that it admits not only a polynomial solution but also a linear one, given the existence of the Overfull Conjecture and other results related to edge colouring of cograph subclasses. From this observation, we propose a conjecture, based on evidence drawn from a computer program specially designed for generation of cographs. The conjecture applies to the join operation when one of the operands has an acyclic core. In addition, we present two theorems for more restricted cases of the conjecture: when the acyclic core is edgeless and when there is a matching which does not cover the core of the other graph. |
| Palabras clave : | Cografos Coloração de arestas Computadores (ciência da computação) Computação gráfica |
| Language: | por |
| Country: | Brasil |
| Editorial : | Universidade Federal da Fronteira Sul |
| Acronym of the institution: | UFFS |
| College, Institute or Department: | Campus Chapecó |
| Type of Access: | Acesso Aberto |
| URI : | https://rd.uffs.edu.br/handle/prefix/1205 |
| Fecha de publicación : | 2014 |
| Aparece en las colecciones: | Ciência da Computação |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| LIMA.pdf | 1,12 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.