Coloração de arestas em grafos indiferença

Abstract

This work investigates techniques for edge coloring in indifference graphs, a subclass of interval graphs. The main objective is to study the minimum number of colors required for a proper edge coloring, with emphasis on the analysis and adaptation of existing coloring constructions. The research focuses on indifference graphs with even maximum degree, for which the chromatic index is not known in general. The methodology includes the analysis of results from the literature, the structural characterization of indifference graphs with exactly four maximal cliques, and the extension of a known coloring construction for indifference graphs with three maximal cliques. The results identify a subclass of indifference graphs with exactly four maximal cliques for which it is proved that a graph is Class 1 if and only if it is not subgraph-overfull, under certain conditions on the sizes of its true-twin classes. The proof is constructive and provides a proper edge coloring with Δ(𝐺) colors for every graph 𝐺 satisfying these conditions. Thus, this work extends the known cases of indifference graphs whose chromatic index can be determined.