Coloração de arestas em grafos split com grau máximo par ; Edge coloring of split graphs with even maximum degree

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. ; Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) ; Universidade Tecnológica Federal do Paraná (UTFPR) ; 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 é ...