Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/31825| Título: | Coloração total equilibrada em grafos com vértice universal |
| Título(s) alternativo(s): | Equitable total coloring in graphs with universal vertex |
| Autor(es): | Gonçalves, Matheus |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Teoria dos grafos Coloração Algorítmos computacionais Otimização combinatória Graph theory Coloring Computer algorithms Combinatorial optimization |
| Data do documento: | 7-Dez-2022 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | GONÇALVES, Matheus. Coloração total equilibrada em grafos com vértice universal. 2022. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2022. |
| Resumo: | Uma coloração total própria de um grafo e uma atribuição de cores para seus vértices e arestas de maneira que quaisquer dois elementos adjacentes ou incidentes tenham cores diferentes. Uma coloração total equilibrada e uma coloração total própria tal que quaisquer duas cores sejam utilizadas a mesma quantidade de vezes ou com uma diferença de no máximo um. O Problema da Coloração Total Equilibrada e, dado um grafo, determinar o índice cromático total equilibrado para esse grafo. Este trabalho apresenta uma técnica para coloração total equilibrada ótima dos grafos em que pelo menos metade dos vértices são universais. A técnica apresentada e baseada no conhecido resultado de A. Hilton apresentado em 1990, para a coloração total dos grafos com vértice universal. Outra contribuição e um contraexemplo para a demonstração de Fu (1994), que determinava o numero cromático total equilibrado dos grafos com vértice universal. |
| Abstract: | A proper total coloring of a graph is an assignment of colors to its vertices and edges such that any two adjacent or incident elements have distinct colors. An equitable total coloring is a proper total coloring such that any two colors are used the same amount of times or with a difference of at most one. The equitable Total Coloring Problem is, given a graph, to determine the equitable total chromatic number for that graph. This undergraduate thesis presents a technique for an optimal equitable total coloring of graphs with at least half of their vertices as universal vertices. The presented technique is based on a known result of A. Hilton presented in 1990 for the total coloring of graphs with universal vertices. Another contribution is a counterexample to the proof of Fu (1994) that determined the equitable total chromatic number of graphs with universal vertices. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/31825 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracaototalequilibradagrafos.pdf | 658,05 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
