Circular Total Colorings of Cubic Circulant Graphs

Abstract

A $(k,d)$-total coloring ($k,d\in \mathbb{N},k\ge 2d$) of a graph $G$ is an assignment $c$ of colors $\{0,1,\dots ,k-1\}$ to the vertices and edges of $G$ such that $d\le |c(x_i)–c(x_j)|\le k–d$ whenever $x_i$ and $x_j$ are two adjacent edges, two adjacent vertices, or an edge incident to a vertex. The circular total chromatic number ${\chi }_c”(G)$ is defined by

$${\chi }_c”(G)=inf\{k/d:G\text{ has a }(k,d)\text{-total coloring}\}.$$

It was proved that $\chi ”(G)–1<{\chi }_c^{″}(G)\le {\chi }^{″}(G)$ — where ${\chi }^{″}(G)$ is the total chromatic number of $G$ — with equality for all type-1 graphs and most of the so far considered type-2 graphs. We determine an infinite class of graphs $G$ such that ${\chi }_c^{″}(G)<{\chi }^{″}(G)$ and we list all graphs of order $<7$ with this property.