Caracterização e coloração de arestas em grafos split-co-comparabilidade

Abstract

A characterization of a graph class is the determination of structural properties that uniquely identify the graphs in this class. Those characterizations can give important information that supports many combinatorial problems, such as the Edge Coloring Problem. An edge coloring of a graph G is an assigment of colors to the edges of G such that the colors of any two edges that share a common vertex are distinct. The Edge Coloring Problem is to determine the minimum number of colors that allows an edge coloring for a given graph G. It is known that any simple graph G has an edge coloring with (G)+1 colors, where (G) is the maximum degree of G. However, some graphs G have an edge coloring with (G) colors. It is an NP-complete problem to decide if a graph G has an edge coloring with (G) colors. This work shows new characterizations for split-co-comparability graphs. Using these characterizations, it is determined a subset of split-co-comparability graphs for which the decision version of the Edge Coloring Problem has polynomial time solution.