Full article: Total colorings of some classes of four regular circulant graphs

Formulae display: $MathJax Logo$ ?Mathematical formulae have been encoded as MathML and are displayed in this HTML version using MathJax in order to improve their display. Uncheck the box to turn MathJax off. This feature requires Javascript. Click on a formula to zoom.

Abstract

The total chromatic number, $χ ″ (G)$ is the minimum number of colors which need to be assigned to obtain a total coloring of the graph G. The Total Coloring Conjecture (TCC) made independently by Behzad and Vizing that for any graph, $χ ″ (G) \leq Δ (G) + 2,$ where $Δ (G)$ represents the maximum degree of G. In this paper we obtained the total chromatic number for some classes of four regular circulant graphs.

Keywords:

MSC Classification:

1. Introduction

Let G be a simple graph with vertex set V(G) and edge set E(G). The total coloring of a graph G is an assignment of colors to vertices and edges such that no two adjacent vertices or edges or edges incident to a vertex receives a same color. The total chromatic number of a graph G, denoted by $χ ″ (G),$ is the minimum number of colors required for its total coloring. It is clear that $χ ″ (G) \geq Δ (G) + 1,$ where $Δ (G)$ is the maximum degree of G.

Behzad [Citation1] and Vizing [Citation10] have independently proposed the Total Coloring Conjecture (TCC) which states that any simple graph G, $χ ″ (G) \leq Δ (G) + 2 .$ The graphs that can be totally colored by $Δ (G) + 1$ colors are said to be Type I graphs whereas the graphs which can be colored by $Δ (G) + 2$ colors are said to be Type II graphs. The total coloring is problem NP-complete even for cubic bipartite graph [Citation9]. Good survey of techniques and other results on total coloring can be found in Yap [Citation11], Borodin [Citation2] and Geetha et al. [Citation4]. In this paper, we show that some four regular circulant graphs are Type I.

2. Four regular circulant graphs

For a sequence of positive integers $1 \leq d_{1} < d_{2} < \dots < d_{l} \leq ⌊ \frac{n}{2} ⌋,$ the circulant graph $G = C_{n} (d_{1}, d_{2}, \dots, d_{l})$ has vertex set $V (G) = {0, 1, 2, \dots, n - 1}$ and two vertices x and y are adjacent if $x \equiv (y \pm d_{i}) \mod n$ for some i where $1 \leq i \leq l .$ A power of cycles graph $C_{n}^{k}$ is a graph with vertex set $V (G) = {0, 1, 2, \dots, n - 1}$ and two vertices x and y are adjacent if and only if $| x - y | \leq k .$ It is easy to see that the four regular circulant graph $C_{n} (1, 2) ≅ C_{n}^{2} .$ Campos and de Mello [Citation3] proved that $C_{n}^{2}, n \neq 7,$ are Type I and $C_{7}^{2}$ is Type II. We know that $K_{4, 4}$ is a four regular circulant graph and it is Type II [Citation11]. Geetha et al. [Citation5] have obtained the total chromatic number for some classes of circulant graphs. A Unitary Cayley graph is a circulant graph with vertex set $V (G) = {0, 1, 2, \dots, n - 1}$ and two vertices x and y are adjacent if and only if $\gcd ((x - y), n) = 1 .$ Prajnanaswaroopa et al. [Citation8], proved that almost all Unitary Cayley graphs of even order are Type I and odd order satisfies TCC. In this paper, we considered some classes of four regular circulant graphs of the forpdelm $C_{n} (a, b), 1 \leq a < b \leq ⌊ \frac{n - 1}{2} ⌋ .$

Junior and Sasaki [Citation6] proved that the graphs $C_{n} (2 k, 3)$ are Type I for $n = (8 μ + 6 λ) k,$ with $k \geq 1$ and non-negative integers μ and λ. Riadh Khennoufa and Olivier Togni [Citation7] studied total colorings of circulant graphs and proved that every 4-regular circulant graphs $C_{6 p} (1, k), p \geq 3$ and $k < 3 p$ with $k \equiv 1 \mod 3$ or $k \equiv 2 \mod 3,$ are Type I. Other cases are still open.

Also they proved that the total chromatic number of $C_{5 p} (1, k),$ with $k < \frac{5 p}{2}, k \equiv 2 \mod 5, k \equiv 3 \mod 5$ is 5. In the following theorem, we prove that the graphs $C_{5 p} (1, k)$ are Type I for the remaining cases $k \equiv 1 \mod 5$ and $k \equiv 4 \mod 5 .$

Theorem 2.1.

The circulant graphs $C_{5 p} (a, b)$ , where $p \geq 1, a, b \equiv 0 \mod 5$ , are Type I.

Proof.

Let $q_{1} = \gcd (5 p, a)$ and $q_{2} = \gcd (5 p, b) .$ The circulant graphs $G = C_{5 p} (a, b)$ are four regular graphs with q₁ cycles of order $\frac{5 p}{q_{1}}$ and q₂ cycles of order $\frac{5 p}{q_{2}} .$

Let $φ : V (G) \cup E (G) \to C = {0, 1, 2, 3, 4}$ be a mapping of G defined as follows.

The vertices v_i of $C_{5 p} (a, b)$ can be colored by $φ (v_{i}) = i \mod 5, 0 \leq i \leq 5 p - 1 .$

Since, all the four regular graphs $C_{5 p} (a, b), C_{5 p} (b, a), C_{5 p} (5 p - a, b)$ and $C_{5 p} (a, 5 p - b)$ are isomorphic to each other, for the edge colorings, we need to consider the three cases.

Case 1: $a \equiv 1 \mod 5$ and $b \equiv 1 \mod 5 .$

The edges of cycles can be colored by setting $φ (v_{i} v_{(i + a) \mod 5}) = (i + 2) \mod 5$ and $φ (v_{i} v_{(i + b) \mod 5}) = (i + 4) \mod 5 .$ If $φ (v_{i}) = c$ where $c \in C,$ then $φ (v_{i} v_{(i + a) \mod 5}) = (c + 2) \mod 5,$ $φ (v_{(i - a) \mod 5} v_{i}) = (c + 1) \mod 5, φ (v_{i} v_{(i + b) \mod 5)} = (c + 4) \mod 5$ and $φ (v_{(i - b) \mod 5} v_{i}) = (c + 3) \mod 5 .$

Case 2: $a \equiv 2 \mod 5$ and $b \equiv 2 \mod 5 .$

The edges of cycles can be colored by setting $φ (v_{i} v_{(i + a) \mod 5}) = (i + 3) \mod 5$ and $φ (v_{i} v_{(i + b) \mod 5}) = (i + 4) \mod 5 .$ If $φ (v_{i}) = c$ where $c \in C,$ then $φ (v_{i} v_{(i + a) \mod 5}) = (c + 3) \mod 5, φ (v_{(i - a) \mod 5} v_{i}) = (c + 1) \mod 5, φ (v_{i} v_{(i + b) \mod 5)} = (c + 4) \mod 5$ and $φ (v_{(i - b) \mod 5} v_{i}) = (c + 2) \mod 5 .$

Case 3: $a \equiv 1 \mod 5$ and $b \equiv 2 \mod 5 .$

The edges of cycles can be colored by setting $φ (v_{i} v_{(i + a) \mod 5}) = (i + 3) \mod 5$ and $φ (v_{i} v_{(i + b) \mod 5}) = (i + 1) \mod 5 .$ If $φ (v_{i}) = c$ where $c \in C,$ then $φ (v_{i} v_{(i + a) \mod 5}) = (c + 3) \mod 5,$ $φ (v_{(i - a) \mod 5} v_{i}) = (c + 2) \mod 5, φ (v_{i} v_{(i + b) \mod 5)} = (c + 1) \mod 5$ and $φ (v_{(i - b) \mod 5} v_{i}) = (c + 4) \mod 5 .$

Therefore, five colors are used for totally color the graph. □

In the following theorem, we prove some classes of four regular circulant graphs $C_{n} (a, b)$ of order 3p are Type I.

Theorem 2.2.

Let p be an odd integer. Then circulant graphs $C_{3 p} (a, b)$ with $\gcd (a, b) = 1$ and $\frac{3 p}{\gcd (3 p, b)} = 3 s, s \in N$ are Type I.

Proof.

Let $q_{1} = \gcd (3 p, a)$ and $q_{2} = \gcd (3 p, b) .$ The circulant graphs $G = C_{3 p} (a, b)$ are four regular graphs with q₁ cycles of order $\frac{3 p}{q_{1}}$ and q₂ cycles of order $\frac{3 p}{q_{2}} .$ Let $φ : V (G) \cup E (G) \to {0, 1, 2, 3, 4}$ be a mapping obtained by the following process.

Let C_i be the cycles of order $\frac{3 p}{q_{2}}$ with the vertices v_ia, $0 \leq i \leq q_{2} - 1 .$ First, we consider the cycle C₀. If $q_{2} = 1,$ then the vertices and edges of C₀ are colored with the colors 0, 3 and 1 cyclically, starting with v₀ receiving the color 0. Otherwise the vertices and edges of C₀ are colored with the colors 3, 1 and 0 cyclically, starting with v₀ receiving the color 1. Now, consider the cycle C₁. The vertices and edges of C₁ are colored with the colors 1, 0 and 4 cyclically, starting with v_a receiving the color 1. For the cycles C_i, $2 \leq i \leq q_{2} - 1,$ if i is even then the vertices and edges of C_i are colored with the colors 0, 2 and 1 cyclically, starting with v_ia receiving the color 0 and i is odd they are colored with the colors 1, 0 and 2 cyclically, starting with v_ia receiving the color.

The edges of cycles of order $\frac{3 p}{q_{1}}$ are colored in the following way: if vertex $v_{i} \in C_{0}$ then $φ (v_{i} v_{(i + a) \mod 3 p}) = 2,$ if $v_{i} \in C_{i}$ where i is odd then $φ (v_{i} v_{(i + a) \mod 3 p}) = 3$ and if $v_{i} \in C_{i}$ where i is even then $φ (v_{i} v_{(i + a) \mod 3 p}) = 4 .$ Therefore, only five colors are used for totally coloring the graph. Hence, $φ$ is a Type I coloring of G. □

For the circulant graphs $C_{n} (a, b)$ where $n = 3 p$ and p is odd, which we considered in the above theorem, the value of b is restricted to factors and multiple of p. In the following theorem, we show that few classes of circulant graphs $C_{n} (1, k)$ where $n = 9 p$ are Type I.

Theorem 2.3.

For each $k \in {2, 3, \dots, ⌊ \frac{9 p - 1}{2} ⌋}$ , every circulant graph $C_{9 p} (1, k)$ with $\frac{9 p}{\gcd (9 p, k)} = 3 s, s \in N$ is Type I.

Proof.

Let $q = \gcd (9 p, k) .$ The circulant graphs $G = C_{9 p} (1, k)$ are four regular graphs with q internal cycles of order $\frac{9 p}{q},$ which are disjoint, and one outer cycle of order 9p. Let $φ : V (G) \cup E (G) \to {0, 1, 2, 3, 4}$ be a mapping obtained by the following process.

Case 1: p is even.

When p is even, 9p will be a multiple of 6. Riadh Khennoufa and Olivier Togni [Citation7] proved that the total chromatic number of $G = C_{6 p} (1, k),$ with $k < \frac{5 p}{2}, k \equiv 1 \mod 3, k \equiv 2 \mod 3$ is 5. From this, one can easily see that the circulant graph $C_{9 p} (1, k),$ where $p \geq 1$ and $k < \frac{9 p}{2}, k \equiv 1 \mod 3, k \equiv 2 \mod 3$ are Type I.

Now, we consider the remaining case, $k \equiv 0 \mod 3 .$

The vertices v_i are colored by $φ (v_{i}) = (i \mod 3 + ⌊ \frac{i}{k} ⌋ \mod 3) \mod 3$ if q = k, else the vertices v_i are colored by $φ (v_{i}) = (2 i \mod 3 - ⌊ \frac{i}{3} ⌋ \mod 3) \mod 3 .$ The edges of the internal cycles can be colored by setting $φ (v_{i} v_{(i + k) \mod 9 p}) = (2 φ (v_{(i + k) \mod 9 p}) - φ (v_{i})) \mod 3 .$ In this coloring process, the vertices and the internal edges of G are colored using only three colors 0, 1 and 2. Now, the edges of the outer cycle can be colored by two colors 3 and 4 as it is of even order. Therefore, five colors are used for total coloring the graph, hence the graph $C_{9 p} (1, k)$ is Type I.

Case 2: p is odd.

The case when $q \neq 1,$ follows from Theorem 2.2. Now, we consider the case when $q = 1 .$

Sub case 2.1: $k \equiv 1 \mod 9$

The vertices v_i where $0 \leq i \leq 9 p - 1$ of G can be colored by $φ (v_{i}) = i \mod 3 + (⌊ \frac{i}{3} ⌋ \mod 3) ⌊ \frac{i \mod 3}{2} ⌋ .$ The edges of the internal cycles can be colored by setting if $i \equiv 1 \mod 3$ then $φ (v_{i} v_{(i + k) \mod 9 p}) = φ (v_{(i + k) \mod 9 p}) + 1 - 3 ⌊ \frac{φ (v_{(i + k) \mod 9 p} v_{i}) \mod 5}{5} ⌋$ else by $φ (v_{i} v_{(i + k) \mod 9 p}) = φ (v_{(i + 2 k) \mod 9 p}) .$ The colors used for vertex v_i and edges incident to it is given in the table below as an ordered triplet $(φ (v_{i}), φ (v_{(i - k) \mod 9 p} v_{i}), φ (v_{i} v_{(i + k) \mod 9 p})) .$

Table

Display Table

The common missing color for vertices v_i and $v_{i + 1}$ can be used for coloring the edge $v_{i} v_{i + 1} .$ Therefore, five colors are used for totally coloring the graph, hence $G = C_{9 p} (1, k)$ is Type I.

Sub case 2.2: $k \equiv 4 \mod 9.$

The vertices v_i where $0 \leq i \leq 9 p - 1$ of G can be colored by $φ (v_{i}) = i \mod 3 + (⌈ \frac{i}{3} ⌉ \mod 3) ⌊ \frac{i \mod 3}{2} ⌋ .$ The edges of the internal cycles can be colored by setting if $i \equiv 1 \mod 3$ then $φ (v_{i} v_{(i + k) \mod 9 p}) = φ (v_{(i + k) \mod 9 p} + 1)$ else by $φ (v_{i} v_{(i + k) \mod 9 p}) = φ (v_{(i + 2 k) \mod 9 p}) .$ The colors used for vertex v_i and edges incident to it is given in the table below as an ordered triplet $(φ (v_{i}), φ (v_{(i - k) \mod 9 p} v_{i}), φ (v_{i} v_{(i + k) \mod 9 p}))$

Table

Display Table

Sub case 2.3: $k \equiv 7 \mod 9.$

The vertices v_i where $0 \leq i \leq 9 p - 1$ of G can be colored by $φ (v_{i}) = i \mod 3 + (⌊ \frac{i}{3} ⌋ \mod 3) ⌊ \frac{i \mod 3}{2} ⌋ .$ The edges of the internal cycles can be colored by setting $φ (v_{i} v_{(i + k) \mod 9 p}) = φ (v_{(i + k + 1) \mod 9 p}) .$ The colors used for vertex v_i and edges incident to it is given in the table below as an ordered triplet $(φ (v_{i}), φ (v_{(i - k) \mod 9 p} v_{i}), φ (v_{i} v_{(i + k) \mod 9 p})) .$

Table

Display Table

The common missing color for vertices v_i and $v_{i + 1}$ can be used for coloring the edge $v_{i} v_{i + 1} .$ Therefore, five colors are used for the total coloring the graph, hence $G = C_{9 p} (1, k)$ is Type I.

In Theorem 2.2, we considered few classes of circulant graph $C_{n} (a, b)$ of order $n = 3 p,$ where p is an odd integer. Now, in the following theorem, we consider few classes of $C_{n} (a, b)$ of order $n = 6 p .$

Theorem 2.4.

Every circulant graph $C_{6 p} (a, b)$ where $a, b \equiv 0 \mod 3$ is Type I, if p is even. Also, $C_{6 p} (a, b)$ where $a, b \equiv 0 \mod 3$ is Type I, if p is odd and $\gcd (a, b) = 1 .$

Proof.

Let $q_{1} = \gcd (6 p, a)$ and $q_{2} = \gcd (6 p, b) .$ The circulant graphs $G = C_{6 p} (a, b)$ are four regular graphs with q₁ cycles of order $\frac{6 p}{q_{1}}$ and q₂ cycles of order $\frac{6 p}{q_{2}} .$ The circulant graphs considered in the hypothesis can be colored in a similar manner irrespective of p being odd or even, if $\frac{6 p}{q_{1}}$ is odd we swap the value of a and b, as graph $C_{n} (a, b)$ is isomorphic to $C_{n} (b, a) .$ Let $φ : V (G) \cup E (G) \to {0, 1, 2, 3, 4}$ be a mapping.

The vertices v_i are colored by $φ (v_{i}) = i \mod 3$ and the edges of cycles of order $\frac{6 p}{q_{2}}$ be colored by setting $φ (v_{i} v_{(i + a) \mod 6 p}) = (2 φ (v_{(i + a) \mod 3 p}) - φ (v_{i})) \mod 3 .$ Now, the edges of cycle $\frac{6 p}{q_{1}}$ with two colors 3 and 4 as it is a cycle with even order. Therefore, five colors are used for the total coloring $φ$ of the graph, hence graph G is Type I. □

Acknowledgements

The authors thank the anonymous reviewers for their careful look and several valuable suggestions that helped us improve the presentation.

Additional information

Funding

This research work was supported by SERB, India (No. SERB: EMR/2017/001869).

References

Behzad, M. (1965). Graphs and their chromatic numbers Doctoral Thesis. Michigan State University.
Google Scholar
Borodin, O. V. (1989). On the total colouring of planar graphs. J. Reine Angew. Math. 394: 180–185.
Web of Science ®Google Scholar
Campos, C. N, De Mello, C. P. (2003). Total colouring of Cn2. Tendencias em Matematica Aplicada e Computacional 4(2): 177–186.
Google Scholar
Geetha, J., Narayanan, N, Somasundaram, K. Total coloring—A survey. https://arxiv.org/abs/1812.05833.
Google Scholar
Geetha, J., Somasundaram, K, Fu, H. L. (2021). Total colorings of circulant graphs. Discrete Math. Algorithm. Appl. 13(05): 2150050.
Web of Science ®Google Scholar
Junior, M. N. A, Sasaki, D. (2020). A result on total coloring of circulant graphs. Anais do V Encontro de Teoria da Computação SBC: 81–84.
Google Scholar
Khennoufa, R, Togni, O. (2008). Total and fractional total colourings of circulant graphs. Discrete Math. 308(24): 6316–6329.
Web of Science ®Google Scholar
Prajnanaswaroopa, S., Geetha, J, Somasundaram, K. Total coloring for some classes of Cayley graphs. https://arxiv.org/abs/2006.07677.
Google Scholar
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math. 78(3): 315–319.
Web of Science ®Google Scholar
Vizing, V. G. (1968). Some unsolved problems in graph theory (in Russian). Russ. Math. Surv. 23(6): 125–141.
Google Scholar
Yap, H. P. (1996). Total Colourings of Graphs. Lecture Notes in Mathematics, Vol. 1623. Berlin: Springer.
Google Scholar

Total colorings of some classes of four regular circulant graphs

Abstract

1. Introduction

2. Four regular circulant graphs

Acknowledgements

References

Information for

Open access

Opportunities

Help and information

Total colorings of some classes of four regular circulant graphs

Abstract

1. Introduction

2. Four regular circulant graphs

Acknowledgements

Additional information

Funding

References

Related research

To cite this article:

Download citation

Your download is now in progress and you may close this window

Login or register to access this feature

Information for

Open access

Opportunities

Help and information

Keep up to date