Coloração total semiforte de grafos tripartidos completos

Abstract

An adjacent vertex distinguishing total coloring is a coloring on the vertices and edges of a graph such that adjacent edges and its common vertex have distinguishing colors, and for every two adjacent vertices their colors-sets are distinct. The Adjacent Vertex Distinguishing Total Coloring Problem is, given a graph G, determine the smallest number of colors that allows an adjacent vertex distinguishing total coloring of G. This number is called adjacent vertex distinguishing total chromatic number and is denoted X " a (G). A k-partite graph is a graph whose graph vertices can be partitioned into k disjoint sets so that no two vertices within the same set are adjacent. A graph is a complete k-partite if every pair of graph vertices in the k sets are adjacent. In the k = 3 case of a complete k-partite graph, the graph is also known as complete tripartite graph. This work presents new results on the number of colors required to do a proper adjacent vertex distinguishing total coloring of complete tripartite graphs, reaching the conclusion that if the graph is complete tripartite, then X" a(G) <= ∆(G) + 2. More specifically it is proved that if G is a complete tripartite graph whose the three disjoint sets have the same cardinality, then its adjacent vertex distinguishing total chromatic number is ∆(G) + 2, and if two disjoint sets have size p and the third part has a higher cardinality than p, then its adjacent vertex distinguishing total chromatic number is less than or equal to ∆(G)+2.