Sobre a coloração total semiforte

The adjacent-vertex-distinguishing-total-colouring (AVD-total-colouring) problem was introduced and studied by Zhang et al. around 2005.This problem consists in associating colours to the vertices and edges of a graph G = (V (G), E(G)) using the least number of colours, such that: (i) any two adjacent vertices or adjacent edges receive distinct colours; (ii) each vertex receive a colour different from the colours of its incident edges; and (iii) for any two adjacent vertices u, v ∈ V (G), the set of colours that color u and its incident edges is distinct from the set of colours that color v and its incident edges.The smallest number of colours for which a graph G admits an AVD-total-colouring is named its AVDtotal chromatic number.Zhang et al. determined the AVD-total chromatic number for some classical families of graphs and noted that all of them admit an AVD-total-colouring with no more than ∆(G) + 3 colours.Based on this observation, the authors conjectured that ∆(G) + 3 colours would be sufficient to construct an AVD-total-colouring for any simple graph G.This conjecture is called the AVD-Total-Colouring Conjecture and remains open for arbitrary graphs, having been verified for a few families of graphs.In this dissertation, we present an overview of the main existing results related to the AVD-total-colouring of graphs.Furthermore, we determine the AVD-total-chromatic number for the following families of graphs: simple graphs with ∆(G) = 3 and without adjacent vertices of maximum degree; flower-snarks; Goldberg snarks; generalized Blanuša snarks; Loupekine snarks; and complete equipartite graphs of even order.We verify that the graphs of these families have AVD-total-chromatic number at most ∆(G) + 2. Additionally, we verify that the AVD-Total-Colouring Conjecture is true for tripartite graphs and complete equipartite graphs of odd order.These results confirm the validity of the AVD-Total-Colouring Conjecture for all the families considered in this dissertation.ix Resumo O problema da coloração total semiforte foi introduzido por Zhang et al. por volta de 2005.Este problema consiste em associar cores às arestas e aos vértices de um grafo G = (V (G), E(G)), utilizando o menor número de cores possível, de forma que: (i) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (ii) cada vértice tenha cor diferente das cores das arestas que nele incidem; e, além disso, (iii) para quaisquer dois vértices adjacentes u, v ∈ V (G), o conjunto das cores que colorem u e suas arestas incidentes é distinto do conjunto das cores que colorem v e suas arestas incidentes.Denominamos esse menor número de cores para o qual um grafo admite uma coloração total semiforte como número cromático total semiforte.Zhang et al. também determinaram o número cromático total semiforte de algumas famílias clássicas de grafos e observaram que todas elas possuem uma coloração total semiforte com no máximo ∆(G) + 3 cores.Com base nesta observação, eles conjeturaram que ∆(G) + 3 cores seriam suficientes para construir uma coloração total semiforte para qualquer grafo simples G. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e permanece aberta para grafos arbitrários, tendo sido verificada apenas para algumas famílias de grafos.Nesta dissertação, apresentamos uma resenha dos principais resultados existentes envolvendo a coloração total semiforte.Além disso, determinamos o número cromático total semiforte para as seguintes famílias: os grafos simples com ∆(G) = 3 e sem vértices adjacentes de grau máximo; os snarks-flor; os snarks de Goldberg; os snarks de Blanuša generalizados; os snarks de Loupekine LP 1 ; e os grafos equipartidos completos de ordem par.Verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a ∆(G) + 2. Investigamos também a coloração total semiforte dos grafos tripartidos e dos grafos equipartidos completos de ordem ímpar e verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a ∆(G) + 3. Os resultados obtidos confirmam a validade da Conjetura da Coloração Total Semiforte para todas as famílias consideradas nesta dissertação.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.