Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/31612| Título: | Coloração de arestas em grafos split com grau máximo par |
| Título(s) alternativo(s): | Edge coloring of split graphs with even maximum degree |
| Autor(es): | Cararo, Cintia Izabel |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Algoritmos Otimização combinatória Teoria dos grafos Algorithms Combinatorial optimization Graph theory |
| Data do documento: | 31-Mai-2023 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | CARARO, Cintia Izabel. Coloração de arestas em grafos split com grau máximo par. 2023. Dissertação (Mestrado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2023. |
| Resumo: | 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. |
| Abstract: | 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. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/31612 |
| Aparece nas coleções: | PG - Programa de Pós-Graduação em Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracaoarestasgrafossplit.pdf | 889,36 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
