Problema da coloração total equilibrada em grafos multipartidos completos

Abstract

A total coloring of a graph is an assignment of colors to its vertices and edges such that adjacent or incident elements receive distinct colors. The smallest positive integer for which a graph has a total coloring is called its total chromatic number. Given a total coloring, if the difference between the cardinalities of any two color classes is at most one, the coloring is called equitable, and the smallest integer satisfying this condition is the equitable total chromatic number of the graph (𝜒′′ 𝑒 ). For this value, Wang (2002) conjectured an upper bound of Δ + 2. A complete multipartite graph is one in which the vertex set can be partitioned into independent sets (parts), with any two vertices from distinct parts being adjacent. When all parts have the same number of vertices, the graph is classified as balanced; otherwise, it is called non-balanced. The objective of this work is to analyze the Equitable Total Coloring Problem in the class of complete multipartite graphs. A literature review was conducted on the main known results classifying balanced complete 𝑟-partite graphs (𝐾𝑟×𝑝) and non-balanced complete tripartite graphs (𝐾𝑝1,𝑝2,𝑝3 ). As a contribution, we determine the exact value of 𝜒′′ 𝑒 for new classes of non-balanced complete multipartite graphs. We prove that, for every 𝑟 ≥ 3, if 𝐺 = 𝐾𝑝1,𝑝2,...,𝑝𝑟 satisfies 𝑝1 < 𝑝2 = 𝑝3 = · · · = 𝑝𝑟, then 𝜒′′ 𝑒 (𝐺) = Δ(𝐺) + 1. Additionally, we determine the equitable total chromatic number of non-balanced complete tripartite graphs 𝐾𝑝1,𝑝2,𝑝3 satisfying 𝑝1 < 𝑝2 ≤ 𝑝3, thereby completing the previously open cases for complete tripartite graphs.