Coloração de arestas para grafos críticos

Abstract

The edge coloring was extensively studied by Vizing in his articles from 1964 and 1965, where he proved very important results such as Vizing’s Theorem and the Adjacency Lemma. Vizing’s Theorem establishes that a graph is either Class 1 or Class 2, and the Adjacency Lemma provides a lower bound for the number of vertices of degree ∆ in the neighborhood of a vertex in a critical graph. The edge recoloring procedure proposed by Vizing was crucial for proving these results. In his thesis, Zatesko (2018) showed an extension of this recoloring procedure, allowing for the optimal coloring of more graphs than with Vizing’s recoloring procedure. This extension considers not only the degrees of the vertices in a graph but also the degrees of the vertices in the neighborhood of a vertex, using concepts such as vertices of the hard core. The objective of this work is to prove extensions to Vizing’s results and other results from the literature using the extended recoloring procedure. So far, this approach has proven to be promising. The results obtained and proven in this work have been peer-reviewed and presented in workshops in the field.