Coloração de arestas em grafos split com grau máximo par

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-8639-3532-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9151881548763857-
Autor(es): dc.contributorSilva, Candida Nunes da-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-4649-0274-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6019111128413167-
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-8639-3532-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9151881548763857-
Autor(es): dc.contributorFigueiredo, Celina Miraglia Herrera de-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-6393-0876-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3957046121364560-
Autor(es): dc.contributorGroshaus, Marina Esther-
Autor(es): dc.contributorhttps://orcid.org/0009-0008-2710-7146-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4281319177692811-
Autor(es): dc.contributorCarmo, Renato José da Silva-
Autor(es): dc.contributorhttps://orcid.org/0000-0003-2630-6852-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2968055170351130-
Autor(es): dc.creatorCararo, Cintia Izabel-
Data de aceite: dc.date.accessioned2025-08-29T13:03:19Z-
Data de disponibilização: dc.date.available2025-08-29T13:03:19Z-
Data de envio: dc.date.issued2023-06-24-
Data de envio: dc.date.issued2023-06-24-
Data de envio: dc.date.issued2023-05-31-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/31612-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1106533-
Descrição: dc.descriptionA proper edge coloring of a graph 𝐺 is an assignment of colors to the edges of 𝐺 such that adjacent edges have distinct colors. The chromatic index of a graph 𝐺, denoted 𝜒′(𝐺), is the minimum number of colors for which 𝐺 has a proper edge coloring. Since every pair of adjacent edges must have distinct colors, 𝜒′(𝐺) ≥ Δ(𝐺), where Δ(𝐺) is the maximum degree of 𝐺. In 1964, Vizing established that 𝜒′(𝐺) ≤ Δ(𝐺) + 1 for any simple graph 𝐺. Graphs with 𝜒′(𝐺) = Δ(𝐺) are said to be Class 1, while graphs with 𝜒′(𝐺) = Δ(𝐺) + 1 are said to be Class 2. Despite the tight bounds for the chromatic index, determining 𝜒′(𝐺) for an arbitrary graph 𝐺 is a difficult computational problem, known to be NP-complete. A graph is split if its vertex set can be partitioned into a clique 𝑄 and a stable set 𝑆. In 2012, Almeida showed that to determine the chromatic index of split graphs it is sufficient to consider the cases where every vertex in 𝑄 has maximum degree. Considering this fact, in this master’s dissertation, we show that if the neighborhood of a subset 𝑋, formed by the vertices of 𝑆 with degree at most Δ(𝐺)/2, has at least ⌊|𝑄|/2⌋ vertices, then 𝐺 is Class 1. In the remaining cases we characterize the subgraph-overfull split graphs.-
Descrição: dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)-
Descrição: dc.descriptionUniversidade Tecnológica Federal do Paraná (UTFPR)-
Descrição: dc.descriptionUma coloração de arestas própria de um grafo 𝐺 é uma atribuição de cores para as arestas de 𝐺 de tal forma que arestas adjacentes possuam cores distintas. O índice cromático de 𝐺, denotado por 𝜒′(𝐺), é o menor número de cores que permitem uma coloração própria de 𝐺. Uma vez que para todo par de arestas adjacentes devem ser atribuídas cores distintas, 𝜒′(𝐺) ≥ Δ(𝐺), onde Δ(𝐺) é o grau máximo de 𝐺. Em 1964, Vizing estabeleceu que 𝜒′(𝐺) ≤ Δ(𝐺) + 1 para qualquer grafo simples 𝐺. Diz-se que um grafo 𝐺 com 𝜒′(𝐺) = Δ(𝐺) é Classe 1 e um grafo 𝐺 com 𝜒′(𝐺) = Δ(𝐺) + 1 é Classe 2. Apesar dos limites justos para o índice cromático, o problema de determiná-lo para um grafo arbitrário é computacionalmente difícil, sabidamente NP-completo. Um grafo é split se seu conjunto de vértices pode ser particionado em uma clique 𝑄 e um conjunto independente 𝑆. Em 1995, Chen, Fu e Ko mostraram que todo grafo split com grau máximo ímpar é Classe 1. Dentre os grafos split com grau máximo par que possuem o índice cromático conhecido, há alguns que são Classe 1 e outros que são Classe 2. Em 2012, Almeida provou que, para determinar o índice cromático dos grafos split, é suficiente considerar os casos em que todo vértice da clique tem grau máximo. Considerando isto, nesta dissertação, mostramos que se a vizinhança do subconjunto 𝑋, formado pelos vértices de 𝑆 com grau no máximo Δ(𝐺)/2, tem pelo menos ⌊|𝑄|/2⌋ vértices, então 𝐺 é Classe 1. Nos casos restantes, nós caracterizamos os grafos split que são subgrafo-sobrecarregados.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPonta Grossa-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Ciência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by/4.0/-
Palavras-chave: dc.subjectAlgoritmos-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectCombinatorial optimization-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectEngenharia/Tecnologia/Gestão-
Título: dc.titleColoração de arestas em grafos split com grau máximo par-
Título: dc.titleEdge coloring of split graphs with even maximum degree-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.