1. Repositório Institucional da Universidade Tecnológica Federal do Paraná (RIUT)
  2. GRAD - Cursos de Graduação
  3. TCC - Trabalhos de Conclusão de Curso de Graduação
  4. Ponta Grossa
  5. PG - Ciência da Computação
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/37257
Registro completo de metadados
Campo DCValorIdioma
dc.creatorPorto, Rafael-
dc.date.accessioned2025-06-26T15:31:53Z-
dc.date.available2025-06-26T15:31:53Z-
dc.date.issued2023-12-07-
dc.identifier.citationPORTO, Rafael. Coloração total de grafos split. 2023. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2023.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/37257-
dc.description.abstractA proper total coloring for a graph is an assignment of colors to its vertices and edges such that any two adjacent vertices have distinct colors, any two edges sharing a vertex have distinct colors, and any vertex has a color different from the colors of the edges incident on it. The Total Coloring Problem is, given a graph 𝐺, to determine the minimum number of colors that allows a total coloring of 𝐺. This number is called the total chromatic number of 𝐺. Given a graph 𝐺 and an integer 𝑘, deciding if 𝐺 has a total coloring with 𝑘 colors is an 𝒩𝒫-complete problem. For split graphs with even maximum degree, the total chromatic number is known. In this work, we extend results from the Edge Coloring Problem in split graphs with even maximum degree to the Total Coloring Problem in split graphs with odd maximum degree.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/4.0/pt_BR
dc.subjectAlgorítmospt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectAlgorithmspt_BR
dc.subjectCombinatorial optimizationpt_BR
dc.subjectGraph theorypt_BR
dc.titleColoração total de grafos splitpt_BR
dc.title.alternativeTotal coloring of split graphspt_BR
dc.typebachelorThesispt_BR
dc.description.resumoUma coloração total própria para um grafo é uma atribuição de cores para seus vértices e arestas de forma que quaisquer dois vértices adjacentes tenham cores distintas, quaisquer duas arestas que compartilham vértice tenham cores distintas e qualquer vértice tenha cor diferente da cor das arestas que nele incidem. O Problema da Coloração Total é dado um grafo 𝐺, determinar o menor número de cores que permite uma coloração total de 𝐺. Esse número é chamado de número cromático total de 𝐺. Dado um grafo 𝐺 e um número inteiro 𝑘, decidir 𝐺 tem uma coloração total com 𝑘 cores é um problema 𝒩𝒫-completo. Para grafos split com grau máximo par, o número cromático total é conhecido. Neste trabalho estendemos resultados do Problema da Coloração de Arestas em grafos split com grau máximo par, para o Problema da Coloração Total em grafos split com grau máximo ímpar.pt_BR
dc.degree.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Almeida, Sheila Morais de-
dc.contributor.referee1Lima, Alane Marie de-
dc.contributor.referee2Nóbrega, Diana Sasaki-
dc.contributor.referee3Omai, Mayara Midori-
dc.contributor.referee4Almeida, Sheila Morais de-
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentDepartamento Acadêmico de Informáticapt_BR
dc.publisher.programCiência da Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
coloracaototalgrafossplit.pdf297,34 kBAdobe PDFThumbnail
Visualizar/Abrir
Mostrar registro simples do item Recomendar este item Visualizar estatísticas


Este item está licenciada sob uma Licença Creative Commons Creative Commons