Sigma Coloring on Powers of Paths and Some Families of Snarks
Luis Gustavo da Soledade Gonzaga, Sheila Morais de Almeida · Electronic Notes in Theoretical Computer Science · 2019
Consider a vertex coloring of a graph where each color is represented by a natural number. The color sum of a vertex is the sum of the colors of its adjacent vertices. The Sigma Coloring Problem concerns determining the sigma chromatic number of a graph G , σ ( G ), which is the least number of colors for a coloring of G such that the color sum of any two adjacent vertices are different. In this article, we proved that σ ( P n k ) ≤ 3 when 2 ≤ k ≤ n 3 − 1 , and we determined the sigma chromatic number for P n k in the remaining cases. This article also presents the sigma chromatic number for Blanuša 1st and 2nd families of snarks, Flower snarks, Goldberg and Twisted Goldberg snarks.