Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/40774| Título: | Problema da coloração total equilibrada em grafos multipartidos completos |
| Título(s) alternativo(s): | Equitable total coloring problem in complete multipartite graphs |
| Autor(es): | Eusebio, Nicolas Crisostimo |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Teoria dos grafos Cores - Análise Computação Graph theory Colors - Analysis Computer science |
| Data do documento: | 26-Jun-2026 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | EUSEBIO, Nicolas Crisostimo. Problema da coloração total equilibrada em grafos multipartidos completos. 2026. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2026. |
| Resumo: | Uma coloração total em um grafo é uma atribuição de cores aos seus vértices e arestas de modo que elementos adjacentes ou incidentes recebam cores distintas. O menor inteiro positivo para o qual um grafo 𝐺 possui uma coloração total é denotado por 𝜒′′(𝐺) e chamado de número cromático total de 𝐺. Dada uma coloração total para um grafo 𝐺, utilizando uma cor 𝑐, a classe de cor 𝑐 é o conjunto dos elementos coloridos com a cor 𝑐. Se a diferença entre as cardinalidades de quaisquer duas classes de cor for no máximo um, então dizemos que a coloração total é equilibrada. O menor número de cores com que se pode obter uma coloração total equilibrada para um dado grafo 𝐺 é chamado de número cromático total equilibrado de 𝐺 e denotado por 𝜒′′ 𝑒 (𝐺). Wang (2002) conjecturou que para qualquer grafo simples 𝐺, existe uma coloração total equilibrada com Δ(𝐺)+2 cores. Um grafo multipartido é aquele em que o conjunto de vértices pode ser particionado em conjuntos independentes. Um grafo é multipartido completo se, dada uma partição dos vértices em conjuntos independentes, quaisquer dois vértices em partes distintas são adjacentes. Quando todas as partes possuem a mesma cardinalidade, o grafo multipartido completo é balanceado. Um grafo multipartido completo balanceado com 𝑟 partes de tamanho 𝑝 é denotado por 𝐾𝑟×𝑝. O objetivo deste trabalho é analisar o Problema da Coloração Total Equilibrada na classe dos grafos multipartidos completos. Realizou-se uma revisão bibliográfica dos principais resultados conhecidos que classificam os grafos 𝑟-partidos completos balanceados e os grafos tripartidos completos 𝐾𝑝1,𝑝2,𝑝3 . Como contribuição, determinamos o número cromático total equilibrado para novas classes de grafos multipartidos completos não balanceados. Demonstramos que, para todo 𝑟 ≥ 3, se 𝐺 = 𝐾𝑝1,𝑝2,...,𝑝𝑟 satisfaz 𝑝1 < 𝑝2 = 𝑝3 = · · · = 𝑝𝑟, então 𝜒′′ 𝑒 (𝐺) = Δ(𝐺)+1. Adicionalmente, determinamos o número cromático total equilibrado dos grafos tripartidos completos não balanceados 𝐾𝑝1,𝑝2,𝑝3 tais que 𝑝1 < 𝑝2 ≤ 𝑝3, completando os casos em aberto para os grafos tripartidos completos. |
| Abstract: | A total coloring of a graph is an assignment of colors to its vertices and edges such that adjacent or incident elements receive distinct colors. The smallest positive integer for which a graph has a total coloring is called its total chromatic number. Given a total coloring, if the difference between the cardinalities of any two color classes is at most one, the coloring is called equitable, and the smallest integer satisfying this condition is the equitable total chromatic number of the graph (𝜒′′ 𝑒 ). For this value, Wang (2002) conjectured an upper bound of Δ + 2. A complete multipartite graph is one in which the vertex set can be partitioned into independent sets (parts), with any two vertices from distinct parts being adjacent. When all parts have the same number of vertices, the graph is classified as balanced; otherwise, it is called non-balanced. The objective of this work is to analyze the Equitable Total Coloring Problem in the class of complete multipartite graphs. A literature review was conducted on the main known results classifying balanced complete 𝑟-partite graphs (𝐾𝑟×𝑝) and non-balanced complete tripartite graphs (𝐾𝑝1,𝑝2,𝑝3 ). As a contribution, we determine the exact value of 𝜒′′ 𝑒 for new classes of non-balanced complete multipartite graphs. We prove that, for every 𝑟 ≥ 3, if 𝐺 = 𝐾𝑝1,𝑝2,...,𝑝𝑟 satisfies 𝑝1 < 𝑝2 = 𝑝3 = · · · = 𝑝𝑟, then 𝜒′′ 𝑒 (𝐺) = Δ(𝐺) + 1. Additionally, we determine the equitable total chromatic number of non-balanced complete tripartite graphs 𝐾𝑝1,𝑝2,𝑝3 satisfying 𝑝1 < 𝑝2 ≤ 𝑝3, thereby completing the previously open cases for complete tripartite graphs. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/40774 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| multipartidoscompletostotalequilibrada.pdf | 373,87 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
