Sobre coloração total dos grafos circulantes

Abstract

A circulant graph Cn(d1, d2, • • • , dl) with 1 ≤ di ≤ bn 2 c, where di 6= dj , has vertex set V = {v0, v1, • • • , vn−1} and edge set E = Sl i=1 Ei , where Ei = {e i 0 , ei 1 , • • • , ei n−1} and e i j = vjvj+di , where the indexes of the vertices are considered modulo n. An edge of Ei is called edge of length di . A k-total coloring of a graph G is an assignment of k colors to the vertices and edges (elements) of G so that adjacent or incident elements have different colors. The total chromatic number of G is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. Graphs with χ 00(G) = ∆(G) + 1 are known as Type 1, and graphs with χ 00(G) = ∆(G) + 2 are known as Type 2. Some classical circulant graphs, such as the cycle graphs Cn ' Cn(1), the complete graphs Kn ' Cn(1, 2, ..., bn/2c), and the complete bipartite graphs Kn,n ' C2n(1, 3, 5, ..., k), where k is the biggest odd number such that k ≤ n, have their total chromatic number determined. Furthermore, the total chromatic number of every cubic circulant graph C2n(d, n) was determined by Hackmann and Kemnitz in 2004. There are many results in the well known powers of cycles graphs, an infinite family of circulant graphs Cn(1, 2, ..., k). In 2003, Campos and de Mello proved that Cn(1, 2) is Type 1, except for graph C7(1, 2) which is Type 2, and they conjectured that Cn(1, 2, ..., k), with 2 ≤ k ≤ bn/2c, is Type 2 if and only if n is odd and k < n/3 − 1. Recently, it was proved that this conjecture holds for k = 3 and k = 4. In 2008, Khennoufa and Togni proved that every 4-regular circulant graph C5p(1, k) is Type 1, for any positive integer p and k < 5p/2 with k ≡ 2 mod 5 or k ≡ 3 mod 5; and proved that C6p(1, k) is Type 1, for p ≥ 3 and k < 3p with k ≡ 1 mod 3 or k ≡ 2 mod 3. Furthermore, they vericated some particular cases with the help of the computer. In the same paper, Khennoufa and Togni conjectured that except for a finite number of Type 2, 4-regular circulant graphs are all Type 1. In this work, we studied all the results that envolved the state of art about total coloring of circulant graphs. Futhermore, we contribute to this conjecture by determining the total chromatic number of all graphs of the following three infinite families of 4-regular circulant graphs: Cn(2k, 3), k ≥ 1 and n = (8µ + 6λ)k, for non negative integers µ and λ; C3n(1, 3), for n > 1; and C3λp(1, p), λ ≥ 1 and p ≡ 0 mod 3, suggesting that the conjecture has a positive answer.