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

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.