نبذة مختصرة : 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. ; A coloração total semiforte é uma coloração dos elementos de um grafo onde os vértices e arestas são coloridos de forma que as cores das arestas adjacentes e do vértice em que elas incidem diferem entre si, e para todos os vértices adjacentes os conjuntos de cores usadas são diferentes. O Problema da Coloração Total Semiforte é, dado um grafo G qualquer, determinar o menor número de cores que permite uma coloração total semiforte de G. Esse número é chamado de número cromático total semiforte e denotado por X" a(G). Um grafo k-partido é um grafo cujos vértices podem ser particionados em k partes, onde quaisquer vértices em uma mesma parte são não-adjacentes entre si. Um grafo é k-partido completo se existe aresta entre todos os pares de vértices que estão em partes diferentes. No caso em que k = 3 de um grafo k-partido completo, o grafo é também conhecido como tripatido completo. Este trabalho apresenta novos resultados a nosso conhecimento sobre o número de cores necessárias para uma coloração total semiforte em grafos tripartidos completos, chegando a conclusão de que se o grafo é tripartido completo, então X" a(G) <= ∆(G) + 2. Mais especificamente é provado que se G é um grafo tripartido completo cuja as três partes possuem a mesma cardinalidade, então o seu números cromático total semiforte é ∆(G) + 2, e que se duas partes possuem tamanho p e a terceira parte tem cardinalidade maior que p, então o seu número cromático total semiforte é menor ou igual a ∆(G) + 2.
Processing Request
No Comments.