Coloração de arestas em grafos split-comparabilidade e split-intervalos

Abstract

A proper edge coloring of a graph is an assignment of colors to its edges such that edges incident with the same vertex have distinct colors. The Edge Coloring Problem is answering, given a graph, which is the least number of colors for a proper edge coloring. That number is called the chromatic index and, for a graph 𝐺, it is denoted 𝜒′ (𝐺). By definition, the chromatic index is at least ∆(𝐺), wherein ∆(𝐺) is the largest number of edges incident with the same vertex of the graph 𝐺. In 1964, Vizing proved that 𝜒′(𝐺) ≤ ∆(𝐺) + 1 for every simple graph 𝐺. Therefore, when 𝐺 is a simple graph, ∆(𝐺) ≤ 𝜒′(𝐺) ≤ ∆(𝐺)+1. A graph is Class 1 if its chromatic index equals its maximum degree, and it is Class 2 otherwise. The Graph Classification Problem is deciding if a simple graph is Class 1. Even considering that there are only two possible values for the chromatic index, the Graph Classification Problem is still NP-complete. In 1985, in his famous column "The NP-Completeness Column: an Ongoing Guide”, David Johnson classified some problems in Graph Theory concerning their computational complexity. In some cases, that complexity was still unknown and Johnson identified graph classes for which he considered it would be easier to determine it. On the classes of split, comparability, and intervals graphs, for instance, Johnson considered that determining the computational complexity of the Classification Problem was possibly easy. However, after 35 years, only the computational complexity of the Classification Problem for comparability graphs was determined, being it an NP-complete problem. This thesis presents a polynomial-time solution for the Classification Problem for splitinterval graphs, besides identifying and correcting an issue in the previous proof that determined the chromatic index of split-comparablility graphs.