
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0002-8639-3532 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/9151881548763857 | - |
| Autor(es): dc.contributor | Silva, Candida Nunes da | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0002-4649-0274 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/6019111128413167 | - |
| Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0002-8639-3532 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/9151881548763857 | - |
| Autor(es): dc.contributor | Figueiredo, Celina Miraglia Herrera de | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0002-6393-0876 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/3957046121364560 | - |
| Autor(es): dc.contributor | Groshaus, Marina Esther | - |
| Autor(es): dc.contributor | https://orcid.org/0009-0008-2710-7146 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/4281319177692811 | - |
| Autor(es): dc.contributor | Carmo, Renato José da Silva | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0003-2630-6852 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/2968055170351130 | - |
| Autor(es): dc.creator | Cararo, Cintia Izabel | - |
| Data de aceite: dc.date.accessioned | 2025-08-29T13:03:19Z | - |
| Data de disponibilização: dc.date.available | 2025-08-29T13:03:19Z | - |
| Data de envio: dc.date.issued | 2023-06-24 | - |
| Data de envio: dc.date.issued | 2023-06-24 | - |
| Data de envio: dc.date.issued | 2023-05-31 | - |
| Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/31612 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1106533 | - |
| Descrição: dc.description | A 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.description | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) | - |
| Descrição: dc.description | Universidade Tecnológica Federal do Paraná (UTFPR) | - |
| Descrição: dc.description | Uma 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.format | application/pdf | - |
| Idioma: dc.language | pt_BR | - |
| Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
| Publicador: dc.publisher | Ponta Grossa | - |
| Publicador: dc.publisher | Brasil | - |
| Publicador: dc.publisher | Programa de Pós-Graduação em Ciência da Computação | - |
| Publicador: dc.publisher | UTFPR | - |
| Direitos: dc.rights | openAccess | - |
| Direitos: dc.rights | http://creativecommons.org/licenses/by/4.0/ | - |
| Palavras-chave: dc.subject | Algoritmos | - |
| Palavras-chave: dc.subject | Otimização combinatória | - |
| Palavras-chave: dc.subject | Teoria dos grafos | - |
| Palavras-chave: dc.subject | Algorithms | - |
| Palavras-chave: dc.subject | Combinatorial optimization | - |
| Palavras-chave: dc.subject | Graph theory | - |
| Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
| Palavras-chave: dc.subject | Engenharia/Tecnologia/Gestão | - |
| Título: dc.title | Coloração de arestas em grafos split com grau máximo par | - |
| Título: dc.title | Edge coloring of split graphs with even maximum degree | - |
| Tipo de arquivo: dc.type | livro digital | - |
| Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: