Coloração total equilibrada em grafos com vértice universal

Abstract

A proper total coloring of a graph is an assignment of colors to its vertices and edges such that any two adjacent or incident elements have distinct colors. An equitable total coloring is a proper total coloring such that any two colors are used the same amount of times or with a difference of at most one. The equitable Total Coloring Problem is, given a graph, to determine the equitable total chromatic number for that graph. This undergraduate thesis presents a technique for an optimal equitable total coloring of graphs with at least half of their vertices as universal vertices. The presented technique is based on a known result of A. Hilton presented in 1990 for the total coloring of graphs with universal vertices. Another contribution is a counterexample to the proof of Fu (1994) that determined the equitable total chromatic number of graphs with universal vertices.