Equitable Total Coloring of Small Cubic Graphs
Autores
|
7105 |
3133,257,3118
|
|
|
7106 |
3133,257,3118
|
|
|
7107 |
3133,257,3118
|
Informações:
Publicações do PESC
Uma k-coloração total de um grafo simples G = (V, E) atribui no máximo k cores aos vértices e arestas de G tal que cores distintas são atribuídas a cada par de vértices adjacentes em V, a cada par de arestas adjacentes em E, e cada vértice e suas arestas incidentes. Uma coloração total é equilibrada se as cardinalidades de quaisquer duas classes de cores diferem em no máximo 1.
Em 2020, Stemock considerou as colorações totais equilibradas de grafos cúbicos em seu artigo "On the equitable total (k+1)-coloring of k-regular graphs''. O autor conjecturou que toda 4-coloração total de um grafo cúbico é equilibrada se n<20. Este limite superior foi motivado por um grafo com n= 20 encontrado no artigo ``On the equitable total chromatic number of cubic graphs'' de Dantas et al. que é Tipo 1, mas não possui uma coloração total equilibrada com 4 cores. Esta conjectura torna-se relevante quando percebemos que se refere a mais de 40.000 grafos, fato que pode ser verificado no site ``House of Graphs''. Encontramos grafos cúbicos que servem como contraexemplos para a conjectura de Stemock e os exibimos no texto.
Em seguida, estudamos os grafos cúbicos para n<20 e conseguimos determinar que uma 4-coloração total será necessariamente equilibrada em grafos cúbicos de 6, 8, 10, e 14 vértices. Além disso, provamos que um grafo cúbico de 12 vértices é o menor contraexemplo possível para a conjectura de Stemock.
A k-total coloring of a simple graph G = (V, E) assigns at most k colors to the vertices and edges of G such that distinct colors are assigned to every pair of adjacent vertices in V, to every pair of adjacent edges in E, and each vertex and its incident edges. A total coloring is equitable if the cardinalities of any two color classes differ by at most 1.
In 2020, Stemock considered equitable total colorings of cubic graphs in his article ``On the equitable total (k+1)-coloring of k-regular graphs''. The author conjectured that every 4-total coloring of a cubic graph is equitable if n<20. This upper bound was motivated by a graph with n= 20 in the article ``On the equitable total chromatic number of cubic graphs'' by Dantas et al. that is Type 1 but does not have an equitable total coloring with 4 colors. This conjecture becomes relevant when we realize that it refers to more than 40000 graphs, which can be verified in the website ``House of Graphs''. We find cubic graphs that serve as counterexamples to the Stemock's conjecture and display them in the text.
Then, we studied the cubic graphs for n<20 and were able to determine that a 4-total coloring is necessarily equitable on cubic graphs of 6, 8, 10, and, 14 vertices. Furthermore, we prove that a cubic graph of 12 vertices is the smallest possible counterexample to the Stemock’s conjecture.