Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/40757| Título: | Coloração de arestas em grafos indiferença |
| Título(s) alternativo(s): | Edge coloring of indiference graph |
| Autor(es): | Costa, Gustavo Henrique Amaral |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Cor Teoria dos grafos Computação Color Graph theory Computer science |
| Data do documento: | 18-Jun-2026 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | COSTA, Gustavo Henrique Amaral. Coloração de arestas em grafos indiferença. 2026. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2026. |
| Resumo: | Este trabalho investiga técnicas para a coloração de arestas em grafos indiferença, uma subclasse dos grafos de intervalos. O objetivo principal é estudar o menor número de cores necessário para uma coloração própria de arestas, com ênfase na análise e na adaptação de construções já existentes. A pesquisa concentra-se em grafos indiferença com grau máximo par, para os quais o índice cromático ainda não é conhecido em geral. A metodologia inclui a análise de resultados da literatura, a caracterização estrutural de grafos indiferença com exatamente quatro cliques maximais e a extensão de uma construção de coloração conhecida para grafos indiferença com três cliques maximais. Os resultados identificam uma subclasse dos grafos indiferença com exatamente quatro cliques maximais para a qual se demonstra que o grafo é Classe 1 se e somente se não é subgrafo-sobrecarregado, sob determinadas condições sobre os tamanhos de suas classes de gêmeos verdadeiros. A demonstração é construtiva e fornece uma coloração própria de arestas com Δ(𝐺) cores para qualquer grafo 𝐺 que satisfaça essas condições. Dessa forma, o trabalho amplia os casos conhecidos de grafos indiferença cujo índice cromático pode ser determinado. |
| Abstract: | This work investigates techniques for edge coloring in indifference graphs, a subclass of interval graphs. The main objective is to study the minimum number of colors required for a proper edge coloring, with emphasis on the analysis and adaptation of existing coloring constructions. The research focuses on indifference graphs with even maximum degree, for which the chromatic index is not known in general. The methodology includes the analysis of results from the literature, the structural characterization of indifference graphs with exactly four maximal cliques, and the extension of a known coloring construction for indifference graphs with three maximal cliques. The results identify a subclass of indifference graphs with exactly four maximal cliques for which it is proved that a graph is Class 1 if and only if it is not subgraph-overfull, under certain conditions on the sizes of its true-twin classes. The proof is constructive and provides a proper edge coloring with Δ(𝐺) colors for every graph 𝐺 satisfying these conditions. Thus, this work extends the known cases of indifference graphs whose chromatic index can be determined. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/40757 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracaografosindiferenca.pdf | 630,01 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
