Generalised colouring sums of graphs

Abstract

The notion of the b-chromatic number of a graph attracted much research interests and recently a new concept, namely the b-chromatic sum of a graph, denoted by ${\mathit{\phi }}^{\prime }(G)$, has also been introduced. Motivated by the studies on b-chromatic sum of graphs, in this paper we introduce certain new parameters such as $\mathit{\chi }$-chromatic sum, ${\mathit{\chi }}^{+}$-chromatic sum, $b^{+}$-chromatic sum, $\mathit{\pi }$-chromatic sum and ${\mathit{\pi }}^{+}$-chromatic sum of graphs. We also discuss certain results on these parameters for a selection of standard graphs.

Keywords:

• chromatic number
• $\mathit{\chi }$-chromatic sum
• ${\mathit{\chi }}^{+}$-chromatic sum
• b-chromatic number
• b-chromatic sum
• $b^{+}$-chromatic sum
• Thue chromatic number
• $\mathit{\pi }$-chromatic sum
• ${\mathit{\pi }}^{+}$-chromatic sum

AMS Subject Classifications:

• 05C62
• 05C05
• 05C20
• 05C38

Public Interest Statement

Graph colouring attracted wide interest among researchers since its introduction in the second half of the nineteenth century. Initial studies regarded colours to be distinct in terms of the corresponding numbering of subscripting of colours only. A number of interesting extremal graph theoretic problems were researched well. Colouring sums are more recent and allows for applications where colours may be technologies of kind with some relation between the distinct technologies. It is envisaged that colour products and other mathematical relations between colours will naturally follow as enhanced research fields. It is foreseen that the modelling of metabolic or artificial intelligent structures as “colours” within larger real or virtual living structures of which certain components are modelled as graphs will reveal interesting applications.

1. Introduction

For general notations and concepts in graph theory and digraph theory, we refer to Bondy and Murty (1976), Chartrand and Lesniak (2000), Chartrand and Zhang (2009), Gross and Yellen (2006), Harary (1969), West (2001). Unless mentioned otherwise, all graphs mentioned in this paper are non-trivial, simple, connected, finite and undirected graphs.

Graph colouring has become a fertile research area since its introduction in the second half of nineteenth century. It has numerous theoretical and practical applications. Let us first recall the fact that in a proper colouring of a graph G, no two adjacent vertices in G can have the same colour. The minimum number of colours in a proper colouring of a graph G is called the chromatic number of G, denoted by $\mathit{\chi }(G)$.

Consider a proper k-colouring of a graph G and denote the set of k colours by $\mathcal{C}=\{c_1,c_2,c_3,\dots ,c_k\}$. Also, consider the disjoint subsets of V(G), defined by $V_{c_i}=\{v_j:v_j\mapsto c_i,v_j\in V(G),c_i\in \mathcal{C}\}$, $1\le i\le k$. Clearly, we can see that $V(G)=\bigcup _{i=1}^k{V}_{c_i}$.

The notion of the b-colouring of a graph and the parameter b-chromatic number, $\mathit{\phi }(G)$, of a graph G(V, E), has been introduced in Irving and Manlove (1999) as follows. Let G be a graph on n vertices, say $v_1,v_2,v_3,\dots ,v_n$. The b-chromatic number of G is defined as the maximum number k of colours that can be used to colour the vertices of G, such that we obtain a proper colouring and each colour i, with $1\le i\le k$, has at least one element $x_i$ which is adjacent to a vertex of every colour j, $1\le j\ne i\le k$. Such a colouring is called a b-colouring of G (see Effatin & Kheddouci, 2003; Irving & Manlove, 1999).

The concept of b-chromatic number has attracted much attention and many studies have been made on this parameter (see Effatin & Kheddouci, 2003; Irving & Manlove, 1999; Kok & Sudev, in press; Kouider & Mahéo, 2002; Vaidya & Isaac, 2014; Vaidya & Isaac, 2015; Vivin & Vekatachalam, 2015).

2. General colouring sum of graphs

The notion of the b-chromatic sum of a given graph G, denoted by ${\mathit{\phi }}^{\prime }(G)$, has been introduced in Lisna and Sunitha (2015) as the minimum of sum of colours c(v) of v for all $v\in V$ in a b-colouring of G using $\mathit{\phi }(G)$ colours. Some results on b-chromatic sums proved in Lisna and Sunitha (2015), which are relevant and useful results in our present study, are listed below.

Theorem 2.1

(Lisna & Sunitha, 2015) The b-chromatic sum of a path $P_n$, $n\ge 2$ is$$\begin{array}{c}\hfill {\mathit{\phi }}^{\prime }(P_n)=\begin{array}{cc}\frac{3}{2}(n-1)+3,\hfill & \text{if}n\ge 5,n\text{is odd},\hfill \\ \frac{3n}{2}+1,\hfill & \text{if}n\ge 6,n\text{is even},\hfill \\ 4,\hfill & \text{if}n=3,\hfill \\ \frac{3n}{2},\hfill & \text{if}n\in \{2,4\}.\hfill \end{array}\end{array}$$

Theorem 2.2

Lisna & Sunitha, 2015 The b-chromatic sum of a cycle $C_n$ is given by$$\begin{array}{c}\hfill {\mathit{\phi }}^{\prime }(C_n)=\begin{array}{cc}\frac{3n}{2}+3,\hfill & \text{if}n\text{is even},n\ne 4,\hfill \\ \frac{3}{2}(n-1)+3,\hfill & \text{if}n\text{is odd},\hfill \\ 6,\hfill & \text{if}n=4.\hfill \end{array}\end{array}$$

Theorem 2.3

Lisna & Sunitha, 2015 The b-chromatic sum of a wheel graph $W_{n+1}$ is$$\begin{array}{c}\hfill {\mathit{\phi }}^{\prime }(W_{n+1})=\begin{array}{cc}\frac{3(n-1)}{2}+7,\hfill & \text{if}n\text{is odd},\hfill \\ \frac{3n}{2}+7,\hfill & \text{if}n\text{is even},n\ne 4,\hfill \\ 9,\hfill & \text{if}n=4.\hfill \end{array}\end{array}$$

Theorem 2.4

Lisna & Sunitha, 2015 For a complete bipartite graph $K_{m,n}$ assume without loss of generality that $m\ge n$, then ${\mathit{\phi }}^{\prime }(K_{m,n})=m+2n$.

This interesting new invariant motivates us for studying similar concepts in graph colouring. This leads us to define the concept of the general colouring sum of graphs as follows.

Definition 2.5

Let $\mathcal{C}=\{c_1,c_2,c_3,\dots ,c_k\}$ allows a b-colouring $\mathcal{S}$ of a given graph G. Clearly, there are k! ways of allocating the colours to the vertices of G. The colour weight of colour, denoted by $\mathit{\theta }(c_i)$, is the number of times a particular colour $c_i$ is allocated to vertices. Then, the colouring sum of a colouring $\mathcal{S}$ of a given graph G, denoted by $\mathit{\omega }(\mathcal{S})$, is defined to be $\mathit{\omega }(\mathcal{S})=\sum _{i=1}^{k}i\mathit{\theta }(c_i)$.

In view of the above definition, the b-chromatic sum of a graph G can be viewed as ${\mathit{\phi }}^{\prime }(G)=min\{\sum _{i=1}^{k}i\mathit{\theta }(c_i)\}$, where this sum varies over all b-colourings of G.

In view of Definition 2.5, in this paper we introduce certain other colouring sums of graphs similar to the b-chromatic sum of graphs.

3. $\mathit{\chi }$-Chromatic sum of certain graphs

The notion of the $\mathit{\chi }$-chromatic sum of a graph G with respect to a proper k-colouring of G is introduced as follows.

Definition 3.1

Let $\mathcal{C}=\{c_1,c_2,\dots ,c_k\}$ be a proper colouring of a graph G. Then, the $\mathit{\chi }$-chromatic sum of G, denoted by ${\mathit{\chi }}^{\prime }(G)$, is defined as ${\mathit{\chi }}^{\prime }(G)=min\{\sum _{i=1}^{k}i\mathit{\theta }(c_i)\}$ where the sum varies over all minimum proper colourings of G.

In the following discussion, we investigate the $\mathit{\chi }$-chromatic sum of certain fundamental graph classes. First, we determine the $\mathit{\chi }$-chromatic sum of path graphs in the following theorem.

Theorem 3.2

The $\mathit{\chi }$-chromatic sum of a path $P_n$ is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{\prime }(P_n)=\begin{array}{cc}1,\hfill & \text{if}n=1,\hfill \\ \frac{3n}{2},\hfill & \text{if}n\text{is even},\hfill \\ \frac{3n-1}{2},\hfill & \text{if}n\text{is odd}.\hfill \end{array}\end{array}$$

Proof

Being a bipartite graph, the vertices of a path graph $P_n$ can be coloured using two colours, say $c_1$ and $c_2$. Then, we need to consider the following cases.

(i)	Assume that $n=1$. Then, $P_n\cong K_1$ with a single vertex say $v_1$. Colour this vertex by the colour $c_1$. Hence, $\mathit{\theta }(c_1)=1$. Therefore, ${\mathit{\chi }}^{\prime }(P_n)=1$.
(ii)	Let n be an even integer. Then, the vertices of path $P_n$ can be coloured alternatively by the colours $c_1$ and $c_2$ and hence $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=\frac{n}{2}$. Therefore, ${\mathit{\chi }}^{\prime }(P_n)=1·\frac{n}{2}+2·\frac{n}{2}=\frac{3n}{2}$.
(iii)	Let $n>1$ be an odd integer. Without loss of generality, label the vertices of $P_n$ with odd subscripts by the colour $c_1$ and the vertices with even subscripts by the colour $c_2$. Then, $\mathit{\theta }(c_1)=\frac{n+1}{2}$ and $\mathit{\theta }(c_2)=\frac{n-1}{2}$. Therefore, ${\mathit{\chi }}^{\prime }(P_n)=1·\frac{n+1}{2}+2·\frac{n-1}{2}=\frac{3n-1}{2}$.

$\square$

In a similar way, the $\mathit{\chi }$-chromatic sum of a cycle graph $C_n$ can be determined as follows.

Theorem 3.3

The $\mathit{\chi }$-chromatic sum of a cycle $C_n$ is ${\mathit{\chi }}^{\prime }(C_n)=3\lceil \frac{n}{2}\rceil$.

Proof

Let $\mathcal{C}$ be a proper colouring of the cycle $C_n$. If n is even, $\mathcal{C}$ must contain at least two colours, say $c_1$ and $c_2$ and if n is odd, then $\mathcal{C}$ must contain at least three colours, say $c_1,c_2$ and $c_3$. Then, we consider the following cases.

(i)

Let n be an odd integer. Now, we can assign the colour $c_1$ to the vertices having odd subscripts other than n, the colour $c_2$ to the vertices having even subscripts and the colour $c_3$ to the vertex $v_n$. Hence $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=\frac{n-1}{2}$ and $\mathit{\theta }(c_3)=1$. Therefore, ${\mathit{\chi }}^{\prime }(G)=1·\frac{n-1}{2}+2·\frac{n-1}{2}+3·1=3·\frac{n+1}{2}$.

(ii)

Let n be an even integer. Then, as explained in the previous result, we can assign the colour $c_1$ to the vertices having odd subscripts and the colour $c_2$ to the vertices having even subscripts. Hence $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=\frac{n}{2}$. Therefore, ${\mathit{\chi }}^{\prime }(C_n)=1·\frac{n}{2}+2·\frac{n}{2}=3·\frac{n}{2}$.

Combining the above two cases, we have ${\mathit{\chi }}^{\prime }(C_n)=3·\lceil \frac{n}{2}\rceil$. $\square$

A wheel graph, denoted by $W_{n+1}$, is defined to be the join of a cycle $C_n$ and a trivial graph $K_1$. That is, $W_{n+1}=C_n+K_1$. The $\mathit{\chi }$-chromatic sum of a wheel graph is determined in the following theorem.

Theorem 3.4

The $\mathit{\chi }$-chromatic sum of a wheel graph $W_{n+1}$ is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{\prime }(W_{n+1})=\begin{array}{cc}\frac{3n+11}{2},\hfill & \text{if}n\text{is odd},\hfill \\ \frac{3n+6}{2},\hfill & \text{if}n\text{is even}.\hfill \end{array}\end{array}$$

Proof

Let us denote the central vertex of the wheel $W_{n+1}$ by v and the vertices of the outer cycle of $W_{n+1}$ by $v_1,v_2,v_3,\dots ,v_n$. Let $\mathcal{C}$ be a minimal proper colouring of $W_{n+1}$. Then, $\mathcal{C}$ must contain three colours, say $c_1,c_2,c_3$, if n is even and it must contain four colours, say $c_1,c_2,c_3,c_4$, if n is odd. Hence, we have the following two cases.

(i)

Let n be an even integer. Then, in the outer cycle, $\frac{n}{2}$ vertices have colour $c_1$ and the other $\frac{n}{2}$ vertices have the colour $c_2$. But the central vertex being adjacent to all vertices of the outer cycle must be coloured using a new colour say $c_3$. Therefore, $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=\frac{n}{2}$ and $\mathit{\theta }(c_3)=1$. Hence, ${\mathit{\chi }}^{\prime }(G)=1·\frac{n}{2}+2·\frac{n}{2}+3=\frac{3n+6}{2}$.

(ii)

Let n be an odd integer. Then, in the outer cycle $C_n$, $\frac{n-1}{2}$ vertices have colour $c_1$ and $\frac{n-1}{2}$ vertices have the colour $c_2$ and the remaining one vertex has the colour $c_3$. As mentioned in the above case, the central vertex v must be coloured using a new colour say $c_4$. Therefore, $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=\frac{n-1}{2}$ and $\mathit{\theta }(c_3)=\mathit{\theta }(c_4)=1$ and hence ${\mathit{\chi }}^{\prime }(G)=1·\frac{n-1}{2}+2·\frac{n-1}{2}+3+4=\frac{3n+11}{2}$.

$\square$

The following result describes the $\mathit{\chi }$-chromatic sum of a complete graph $K_n$.

Proposition 3.5

The $\mathit{\chi }$-chromatic sum of a complete graph $K_n$ is ${\mathit{\chi }}^{\prime }(K_n)=\frac{n(n+1)}{2}$.

Proof

We know that in a proper colouring of $K_n$, every vertex has distinct colours. That is, $\mathit{\chi }(K_n)=n$. Therefore, $\mathit{\theta }(c_i)=1$, for all $1\le i\le n$. Hence, we have ${\mathit{\chi }}^{\prime }(K_n)=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$. $\square$

The $\mathit{\chi }$-chromatic sum of a complete bipartite graph is determined in the following result.

Proposition 3.6

The $\mathit{\chi }$-chromatic sum of a complete bipartite graph $K_{m,n}$, $m\ge n$ is ${\mathit{\chi }}^{\prime }(K_{m,n})=m+2n$.

Proof

Assume that G be the complete bipartite graph with a bipartition (X, Y) such that $|X|\ge |Y|$. As a bipartite graph, G is 2-colourable. Since $|X|\ge |Y|$, label every vertex in X by the colour $c_1$ and every vertex of Y by the colour $c_2$. Hence, $\mathit{\theta }(c_1)=|X|$ and $\mathit{\theta }(c_2)=|Y|$. Therefore, ${\mathit{\chi }}^{\prime }(G)=|X|+2|Y|$. $\square$

Let us now recall the definition of a Rasta graph defined in Kok, Sudev, and Sudev (in press) as follows.

Definition 3.7

(Kok et al., in press) For a l-term sum set $\{t_1,t_2,t_3,\dots ,t_l\}$ with $t_1>t_2>t_3>\dots >t_l>1$, define the directed graph $G^{(l)}$ with vertices $V(G^{(l)})=\{v_{i,j}:1\le j\le t_i,1\le i\le l\}$ and the arcs, $A(G^{(l)})=\{(v_{i,j},v_{(i+1),m}):1\le i\le (l-1),1\le j\le t_i$ and $1\le m\le t_{(i+1)}\}$.

In Kok and Sudev (in press), it is shown that for a Rasta graph R corresponding to the underlying graph of $G^{(l)}$ the chromatic number $\mathit{\phi }(R)=2$. Assume, without loss of generality, that $\sum _{i=i}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}\ge \sum _{i=i}^{\lceil \frac{l}{2}\rceil }{t}_{2i}$ if l is even and $\sum _{i=i}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}\ge \sum _{i=i}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i}$ if l is odd. Then, the $\mathit{\chi }$-chromatic sum of R is determined in the following theorem.

Theorem 3.8

The $\mathit{\chi }$-chromatic sum of a Rasta graph R is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{\prime }(R)=\begin{array}{cc}\sum _{i=1}^{\frac{l}{2}}{t}_{(2i-1)}+2\sum _{i=1}^{\frac{l}{2}}{t}_{2i},\hfill & \text{if}l\text{is even},\hfill \\ \sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+2\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i},\hfill & \text{if}l\text{is odd}.\hfill \end{array}\end{array}$$

Proof

 

(i)

Let l be an even integer. Since all vertices corresponding to $t_{(2i-1)}$, $1\le i\le \frac{l}{2}$ are non-adjacent and hence we can colour these vertices by $c_1$. Also, the remaining vertices, corresponding to $t_{2i}$, $1\le i\le \frac{l}{2}$ are also non-adjacent among themselves and these vertices can be coloured using the colour $c_2$. That is, $\mathit{\theta }(c_1)=\sum _{i=1}^{\frac{l}{2}}{t}_{(2i-1)}$ and $\mathit{\theta }(c_2)=\sum _{i=1}^{\frac{l}{2}}{t}_{2i}$. Therefore, in this case ${\mathit{\chi }}^{\prime }(G)=\sum _{i=1}^{\frac{l}{2}}{t}_{(2i-1)}+2\sum _{i=1}^{\frac{l}{2}}{t}_{2i}$.

(ii)

Let l be an odd integer. Then, as explained in the above case, the $\lceil \frac{l}{2}\rceil$ vertices corresponding to $t_{(2i-1)};1\le i\le \lceil \frac{l}{2}\rceil$ are non-adjacent among themselves and hence we can colour these vertices by $c_1$. The remaining $\lfloor \frac{l}{2}\rfloor$ vertices corresponding to $t_{2i},;1\le i\le \lfloor \frac{l}{2}\rfloor$ are also non-adjacent among themselves and hence we can colour these vertices by $c_2$. Therefore, $\mathit{\theta }(c_1)=\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}$ and $\mathit{\theta }(c_2)=\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i}$ and hence ${\mathit{\chi }}^{\prime }(G)=\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+2\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i}$.

$\square$

4. The ${\mathit{\chi }}^{+}$-chromatic sum of certain graphs

We now define a new colouring sum, namely ${\mathit{\chi }}^{+}$-chromatic sum of a given graph G as follows.

Definition 4.1

Let $\mathcal{C}=\{c_1,c_2,\dots ,c_k\}$ be a proper colouring of a graph G. Then, the ${\mathit{\chi }}^{+}$-chromatic sum of a graph G, denoted by ${\mathit{\chi }}^{+}(G)$, is defined as ${\mathit{\chi }}^{+}(G)=max\{\sum _{i=1}^{k}i\mathit{\theta }(c_i)\}$, where the sum varies over all minimum proper colourings of G.

Analogous to the studies on $\mathit{\chi }$-chromatic sum of certain graphs, here we study the ${\mathit{\chi }}^{+}$-chromatic sum of the corresponding graphs.

Theorem 4.2

For $n\ge 1$, the ${\mathit{\chi }}^{+}$-chromatic sum of a path $P_n$ is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{+}(P_n)=\begin{array}{cc}1,\hfill & \text{if}n=1,\hfill \\ \frac{3n}{2},\hfill & \text{if}n\text{is even},\hfill \\ \frac{3n+1}{2},\hfill & \text{if}n\text{is odd}.\hfill \end{array}\end{array}$$

Proof

If $n=1$, we can assign $c_1$ to its unique vertex, which shows that ${\mathit{\chi }}^{+}(P_n)=1$. Hence, let $n>1$. As stated earlier, every path $P_n,n\ge 2$ is 2-colourable. Then, we have to consider the following cases.

(i)	If n is even, as mentioned in Theorem 3.2, the vertices can be coloured alternatively by the colours $c_1$ and $c_2$ and hence in this case, ${\mathit{\chi }}^{+}(P_n)=\frac{3n}{2}$.
(ii)	If n is odd, then the mutually non-adjacent $\frac{n-1}{2}$ vertices are coloured by $c_1$ and the remaining mutually non-adjacent $\frac{n+1}{2}$ vertices can be coloured by the colour $c_2$. Therefore, ${\mathit{\chi }}^{+}(P_n)=1·\frac{n-1}{2}+2·\frac{n+1}{2}=\frac{3n+1}{2}$.

This completes the proof. $\square$

The following is an immediate consequence of Theorem 3.2 and Theorem 4.2.

Corollary 4.3

For a path $P_n$, $n\ge 1$ it follows that, ${\mathit{\chi }}^{+}(P_n)={\mathit{\chi }}^{\prime }(P_n)$ if $n=1$ or even, else ${\mathit{\chi }}^{+}(P_n)={\mathit{\chi }}^{\prime }(P_n)+1$.

In the following result, let us determine the ${\mathit{\chi }}^{+}$-chromatic sum of cycles.

Theorem 4.4

The ${\mathit{\chi }}^{+}$-chromatic sum of a cycle $C_n$ is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{+}(C_n)=\left\{\begin{array}{cc}\frac{3n}{2},\hfill & \text{if}n\text{is even},\hfill \\ \frac{5n-3}{2},\hfill & \text{if}n\text{is odd}.\hfill \end{array}\right.\end{array}$$

Proof

As stated earlier, if n is even, then $C_n$ is 2-colourable and if n is odd, $C_n$ is 3-colourable. Then, we have to consider the following cases.

(i)	Let n be an even integer. Then, the vertices of $C_n$ can be alternatively coloured by two colours $c_1$ and $c_2$. We can see that exactly $\frac{n}{2}$ vertices in $C_n$ have the colours $c_1$ and $c_2$ each. Therefore, $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=\frac{n}{2}$. Therefore, ${\mathit{\chi }}^{+}(C_n)=\frac{3n}{2}$.
(ii)	Let n be an odd integer. Then, we can assign colour $c_3$ to $\frac{n-1}{2}$ vertices, colour $c_2$ to $\frac{n-1}{2}$ vertices and colour $c_1$ to one vertex, which provides a 3-colouring such that $\mathit{\theta }(c_1)=1,\mathit{\theta }(c_2)=\mathit{\theta }(c_3)=\frac{n-1}{2}$. Therefore, ${\mathit{\chi }}^{+}(C_n)=5·\frac{n-1}{2}+1=\frac{5n-3}{2}$.

$\square$

The following theorem describes the ${\mathit{\chi }}^{+}$-chromatic sum of a wheel graph $W_{n+1}$.

Theorem 4.5

The ${\mathit{\chi }}^{+}$-chromatic sum of a wheel graph $W_{n+1}$ is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{+}(W_{n+1})=\left\{\begin{array}{cc}\frac{5n+2}{2},\hfill & \text{if}n\text{is even},\hfill \\ \frac{7n-1}{2},\hfill & \text{if}n\text{is odd}.\hfill \end{array}\right.\end{array}$$

Proof

Let $v_1,v_2,v_3,\dots ,v_n$ be the vertices of the outer cycle the wheel graph and v be its central vertex. We have already mentioned in Theorem 3.4 that if n is even, then $W_{n+1}$ is 3-colourable and if n is odd, then $W_{n+1}$ is 4-colourable. Then, we have the following cases.

(i)

Let n be an even integer. Then, we can assign the colour $c_3$ to $\frac{n}{2}$ vertices of the outer cycle, the colour $c_2$ to the remaining $\frac{n}{2}$ vertices of the outer cycle and the colour $c_1$ to the central vertex. Hence, $\mathit{\theta }(c_3)=\mathit{\theta }(c_2)=\frac{n}{2}$ and $\mathit{\theta }(c_1)=1$. Therefore, ${\mathit{\chi }}^{+}(W_{n+1})=3·\frac{n}{2}+2·\frac{n}{2}+1=\frac{5n+2}{2}$.

(ii)

Let n be an odd integer. Then, we can assign colour $c_3$ to the $\frac{n-1}{2}$ non-adjacent vertices, assign colour $c_3$ to the $\frac{n-1}{2}$ non-adjacent vertices, colour $c_3$ for the remaining single vertex and colour $c_4$ to the central vertex, so that we get $\mathit{\theta }(c_3)=\mathit{\theta }(c_4)=\frac{n-1}{2}$, $\mathit{\theta }(c_2)=1$ and $\mathit{\theta }(c_1)=1$. Therefore, we have ${\mathit{\chi }}^{\prime }(W_{n+1})=4·\frac{n-1}{2}+3·\frac{n-1}{2}+2·1+1·1=\frac{7n-1}{2}$.

$\square$

The following result is an obvious and straightforward result on the ${\mathit{\chi }}^{+}$-chromatic sum of complete graphs.

Proposition 4.6

The ${\mathit{\chi }}^{+}$-chromatic sum of a complete graph $K_n$ is given by ${\mathit{\chi }}^{+}(K_n)={\mathit{\chi }}^{\prime }(G)=\frac{n(n+1)}{2}$.

Proof

Note that $\mathit{\chi }(K_n)=n$ and hence as mentioned in Theorem 3.8, all vertices have distinct colours. That is, we have $\mathit{\theta }(c_i)=1$; for all $1\le i\le n$. Hence, ${\mathit{\chi }}^{+}(K_n)=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$. $\square$

An obvious and straightforward result on the ${\mathit{\chi }}^{+}$-chromatic sum of complete bipartite graphs is given below.

Theorem 4.7

Consider the ${\mathit{\chi }}^{+}$-chromatic sum of a complete bipartite graph $K_{m,n}$, $m\ge n\ge 1$, ${\mathit{\chi }}^{+}(K_{m,n})=2m+n$.

Proof

Since $n\ge m$ the maximum sum is obtained by allocating colour $c_2$ to the n non-adjacent vertices and $c_1$ to the m non-adjacent vertices. So $\mathit{\theta }(c_1)=n$ and $\mathit{\theta }(c_2)=m$. Therefore, ${\mathit{\chi }}^{+}(K_{m,n})=2m+n$. $\square$

The ${\mathit{\chi }}^{+}$-chromatic sum of Rasta graph can be determined as in the following theorem.

Theorem 4.8

The ${\mathit{\chi }}^{+}$-chromatic sum of Rasta graph R is given by$$\begin{array}{c}\hfill {\mathit{\chi }}^{+}(R)=\left\{\begin{array}{cc}2\sum _{i=1}^{\frac{l}{2}}{t}_{(2i-1)}+\sum _{i=1}^{\frac{l}{2}}{t}_{2i},\hfill & \text{if l is even},\hfill \\ 2\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i},\hfill & \text{if l is odd}.\hfill \end{array}\right.\end{array}$$

Proof

 

(i)

Let l be an even integer. Since all $\frac{n}{2}$ vertices, corresponding to $t_{(2i-1)}$, for all $1\le i\le \frac{l}{2}$ are non-adjacent, these vertices can be coloured using the colour $c_2$. By the same reason, the colour $c_1$ is allocated to the vertices corresponding to $t_{2i}$, $1\le i\le \frac{l}{2}$. Hence, $\mathit{\theta }(c_1)=\sum _{i=1}^{\frac{l}{2}}{t}_{2i}$ and $\mathit{\theta }(c_2)=\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}$. Hence, ${\mathit{\chi }}^{+}(R)=2\sum _{i=1}^{\frac{l}{2}}{t}_{(2i-1)}+\sum _{i=1}^{\frac{l}{2}}{t}_{2i}$ for the even values of n.

(ii)

If l is an odd integer, then the $\frac{n+1}{2}$ mutually non-adjacent vertices can be coloured using $c_2$ and the remaining $\frac{n-1}{2}$ mutually non-adjacent vertices can be coloured using $c_1$. Hence, ${\mathit{\chi }}^{+}(R)=2\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i}$, for the odd values of n.

$\square$

5. $b^{+}$-Chromatic Sum of Certain Graphs

Analogous to the $\mathit{\chi }$-chromatic sum and ${\mathit{\chi }}^{+}$-chromatic sum of graphs, we can also define the $b^{+}$ chromatic sum as follows.

Definition 5.1

The $b^{+}$-chromatic sum of a graph G, denoted by ${\mathit{\varphi }}^{+}(G)$, is defined as ${\mathit{\varphi }}^{+}(G)=max\{\sum _{i=1}^{k}i\mathit{\theta }(c_i)\}$, where the sum varies over a minimal b-colouring using $\mathit{\varphi }(G)$ colours.

Now, for determining the respective values of ${\mathit{\phi }}^{+}$ for different graph classes, we use the proof techniques followed in Lisna and Sunitha (2015). Reversing the colouring pattern explained in Lisna and Sunitha (2015), we work out the $b^{+}$-chromatic sum of given graph classes. Hence, we have the following results.

Theorem 5.2

The $b^{+}$-chromatic sum of a path $P_n,n\ge 2$ is given by$$\begin{array}{c}\hfill {\mathit{\phi }}^{+}(P_n)=\left\{\begin{array}{cc}\frac{5n-3}{2},\hfill & \text{if}n\ge 5\text{, n is odd},\hfill \\ \frac{5n-2}{2},\hfill & \text{if}n\ge 6\text{, n is even},\hfill \\ 5,\hfill & \text{if}n=3,\hfill \\ \frac{3n}{2},\hfill & \text{if}n\in \{2,4\}.\hfill \end{array}\right.\end{array}$$

Proof

We know that a b-colouring of a path $P_n$ requires at most three colours. If $1<n\le 4$, the b-chromatic number of $P_n$ is 2. In this context, the following cases are to be considered.

(i)

Let n be even. That is, $n=2,4$. If $n=2$, then, one of its two vertices has colour $c_1$ and the other vertex has colour $c_2$. Hence, the $b^{+}$-chromatic sum of $P_2$ is $2·1+1·1=3$. If $n=4$, Let ${\mathcal{C}}_1=\{v_2,v_4\}$ and ${\mathcal{C}}_2=\{v_1,v_3\}$ be the colour classes of the colours $c_1$ and $c_2$, respectively, so that $\mathcal{C}=\{c_1,c_2\}$ is a b-colouring of $P_n$. Then, the $b^{+}$-chromatic sum of $P_4$ is given by $2·2+1·2=6$. Combining these two cases, it follows that ${\mathit{\phi }}^{\prime }(P_n)={\mathit{\phi }}^{+}(P_n)=\frac{3n}{2}$, for $n=2,4$.

(ii)

Let $n=3$. Then, let ${\mathcal{C}}_1=\{v_2\}$ and ${\mathcal{C}}_2=\{v_1,v_3\}$, so that $\mathcal{C}=\{c_1,c_2\}$ is a $b^{+}$-colouring of $P_n$. Then, the $b^{+}$-chromatic sum of $P_4$ is given by $2·2+1·1=5$.

If $n\ge 5$, the b-chromatic number of a path $P_n$ is 3. Hence, we have to consider the following cases.

(iii)

Let $n\ge 5$ and n be odd. Now, let $\mathcal{C}=\{c_1,c_2,c_3\}$ be a colouring on $P_n$ such that ${\mathcal{C}}_1=\{v_3\}$ be the colour class of the colour $c_1$, ${\mathcal{C}}_2=\{v_2,v_5,v_7,\dots ,v_n\}$ be the colour class of the colour $c_2$ and ${\mathcal{C}}_3=\{v_1,v_4,v_6,\dots ,v_{n-1}\}$ be the colour class of colour $c_3$. Clearly, this colouring is a $b^{+}$-colouring of $P_n$. Then, we have $\mathit{\theta }(c_1)=1,\mathit{\theta }(c_2)=\frac{n-1}{2}$ and $\mathit{\theta }(c_3)=\frac{n-1}{2}$. Hence, for $n\ge 5$ and n is odd, ${\mathit{\phi }}^{+}(P_n)=\frac{3}{2}(n-1)+\frac{2}{2}(n-1)+1=\frac{5n-3}{2}$.

(iv)

Let $n\ge 5$ and n be even. Here, assume that $\mathcal{C}=\{c_1,c_2,c_3\}$ be a colouring on $P_n$ such that the colour classes ${\mathcal{C}}_1,{\mathcal{C}}_2$ and ${\mathcal{C}}_3$ are exactly as defined in the previous case. This colouring is obviously a $b^{+}$ colouring of $P_n$. Then, it follows that $\mathit{\theta }(c_1)=1$, $\mathit{\theta }(c_2)=\frac{n-2}{2}$ and $\mathit{\theta }(c_3)=\frac{n}{2}$. Hence, for $n\ge 6$, k is even, ${\mathit{\phi }}^{+}(P_n)=3·\frac{n}{2}+2·\frac{n-2}{2}+1=\frac{5n-2}{2}$.

$\square$

Similarly, the $b^{+}$-chromatic sum of a cycle $C_n$ is determined in the following theorem.

Theorem 5.3

The $b^{+}$-chromatic sum of a cycle $C_n$ is given by$$\begin{array}{c}\hfill {\mathit{\phi }}^{+}(C_n)=\left\{\begin{array}{cc}6,\hfill & \text{if}n=4,\hfill \\ \frac{5n-3}{2},\hfill & \text{if}n\text{is odd},\hfill \\ \frac{5n-6}{2},\hfill & \text{if n is even,}n\ne 4.\hfill \end{array}\right.\end{array}$$

Proof

First, let $n=4$. It is to be noted that the b-chromatic number of the cycle $C_4$ is 2, where the vertices $v_1$ and $v_3$ have colour $c_1$ and the vertices $v_2$ and $v_4$ have the colour $c_2$. Therefore, the $b^{+}$-chromatic sum of $C_4$ is $2·2+2·1=6$.

Next, assume that $n\ne 4$. We know that the b-chromatic number of a cycle $C_n,n\ne 4$ is 3. Let $\mathcal{C}=\{c_1,c_2,c_3\}$ be a b-colouring of a given cycle $C_n$. Here, we have to consider the following cases.

(i)

Let n be odd. Now a b-colouring which forms the colour classes, ${\mathcal{C}}_1=\{v_3\}$, ${\mathcal{C}}_2=\{v_1,v_4,v_6,\dots ,v_{n-1}\}$ and ${\mathcal{C}}_3=\{v_2,v_5,v_7,\dots ,v_n\}$, yield the desirable b-colouring such that $\mathit{\theta }(c_1)=1$, $\mathit{\theta }(c_2)=\frac{n-1}{2}$ and $\mathit{\theta }(c_3)=\frac{n-1}{2}$. Therefore, here the $b^{+}$-chromatic sum is given by $3·\frac{n-1}{2}+2·\frac{n-1}{2}+1·1=\frac{5n-3}{2}$.

(ii)

Let n be even. Now, a b-colouring which forms the colour classes, ${\mathcal{C}}_1=\{v_3,v_n\}$, ${\mathcal{C}}_2=\{v_1,v_4,v_6,\dots ,v_{n-2}\}$ and ${\mathcal{C}}_3=\{v_2,v_5,v_7,\dots ,v_{n-1}\}$, yield the desirable b-colouring such that $\mathit{\theta }(c_1)=2$, $\mathit{\theta }(c_2)=\frac{n-2}{2}$ and $\mathit{\theta }(c_3)=\frac{n-2}{2}$. Therefore, we have ${\mathit{\phi }}^{+}(C_n)=3·\frac{n-2}{2}+2·\frac{n-2}{2}+2=\frac{5n-6}{2}$.

This completes the proof. $\square$

Now, the $b^{+}$-chromatic sum of a wheel graph $W_{n+1}$ is determined in the following result.

Theorem 5.4

The $b^{+}$-chromatic sum of a wheel graph $W_{n+1}$ is given by$$\begin{array}{c}\hfill {\mathit{\phi }}^{+}(W_{n+1})=\left\{\begin{array}{cc}11,\hfill & \text{if}n=4,\hfill \\ \frac{7n-1}{2},\hfill & \text{if}n\text{is odd},\hfill \\ \frac{7n-4}{2},\hfill & \text{if}n\text{is even},n\ne 4.\hfill \end{array}\right.\end{array}$$

Proof

We have already stated that the b-chromatic number of the cycle $C_4$ is 3. Therefore, a b-colouring of $W_5=C_4+K_1$ must contain 3 colours, say $c_1,c_2$ and $c_3$. Let the corresponding colour classes be ${\mathcal{C}}_1=\{v\},{\mathcal{C}}_2=\{v_1,v_3\}$ and ${\mathcal{C}}_3=\{v_2,v_4\}$, where v is the central vertex of the wheel graph. Then, $\mathit{\theta }(c_1)=1$, $\mathit{\theta }(c_2)=2$ and $\mathit{\theta }(c_3)=2$. Hence, ${\mathit{\phi }}^{+}(W_5)=1·1+2·2+3·2=11$. Next, assume that $n\ne 4$. Then, every b-colouring of $W_{n+1}$ must contain 4 colours. Let $\mathcal{C}=\{c_1,c_2,c_3,c_4\}$ be the required colouring of G. Then, we have to consider the following cases.

(i)

Assume that n is odd. Then, colour the vertices of $W_{n+1}$ using the colours in $\mathcal{C}$ in such a way that the corresponding colour classes are ${\mathcal{C}}_1=\{v\}$, ${\mathcal{C}}_2=\{v_3\}$${\mathcal{C}}_3=\{v_1,v_4,v_6,\dots ,v_{n-1}\}$ and ${\mathcal{C}}_4=\{v_2,v_5,v_7,\dots ,v_n\}$. Therefore, we have $\mathit{\theta }(c_1)=\mathit{\theta }(c_2)=1$ and $\mathit{\theta }(c_3)=\frac{n-1}{2}$ and $\mathit{\theta }(c_4)=\frac{n-1}{2}$. Then, we have ${\mathit{\phi }}^{+}(W_{n+1})=4·\frac{n-1}{2}+3·\frac{n-1}{2}+2+1=\frac{7n-1}{2}$.

(ii)

Assume that n is even. Colour the vertices of $W_{n+1}$ in such a way that the corresponding colour classes are ${\mathcal{C}}_1=\{v\}$, ${\mathcal{C}}_2=\{v_3,v_n\}$${\mathcal{C}}_3=\{v_1,v_4,v_6,\dots ,v_{n-2}\}$ and ${\mathcal{C}}_4=\{v_2,v_5,v_7,\dots ,v_{n-1}\}$. Then, we have $\mathit{\theta }(c_1)=1$, $\mathit{\theta }(c_2)=2$ and $\mathit{\theta }(c_3)=\mathit{\theta }(c_4)=\frac{n-2}{2}$. Hence, ${\mathit{\phi }}^{+}(W_{n+1})=4·\frac{n-2}{2}+3·\frac{n-2}{2}+2·2+1=\frac{7n-4}{2}$.

$\square$

The following theorem describes the ${\mathit{\phi }}^{+}$-chromatic number of a complete bipartite graph.

Theorem 5.5

The $b^{+}$-chromatic sum of a complete bipartite graph $K_{m,n},m\ge n$ is ${\mathit{\phi }}^{+}(K_{m,n})=2m+n$.

Proof

The result follows directly from the proof of Theorem 4.7. $\square$

The b-chromatic sum and the $b^{+}$-chromatic sum of Rasta Graph R is determined in the theorem given below.

Theorem 5.6

The b-chromatic sum of a Rasta graph R is given by$$\begin{array}{c}\hfill {\mathit{\phi }}^{\prime }(R)=\left\{\begin{array}{cc}\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+2\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{2i},\hfill & \text{if l is even},\hfill \\ \sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+2\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i},\hfill & \text{if l is odd},\hfill \end{array}\right.\end{array}$$

and the $b^{+}$-chromatic sum of R is given by$$\begin{array}{c}\hfill {\mathit{\phi }}^{+}(R)=\left\{\begin{array}{cc}2\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{2i},\hfill & \text{if l is even},\hfill \\ 2\sum _{i=1}^{\lceil \frac{l}{2}\rceil }{t}_{(2i-1)}+\sum _{i=1}^{\lfloor \frac{l}{2}\rfloor }{t}_{2i},\hfill & \text{if l is odd}.\hfill \end{array}\right.\end{array}$$

Proof

The proof follows directly from the proofs of Theorem 3.8 and 4.8. $\square$

6. Two Thue chromatic sums of a path

A finite sequence $S=(q_1,q_2,q_3,\dots ,q_t)$ of symbols of any alphabet is known to be non-repetitive if for all its subsequences $(r_1,r_2,r_3,\dots ,r_{2m});1\le m\le \frac{t}{2}$, the condition $r_i\ne r_{2i},\forall 1\le i\le m$, holds.

Let G be a simple undirected graph on n vertices and let a minimum set of colours $\mathcal{C}$ allow a proper vertex colouring of G. If the sequence of vertex colours of any path of even and finite length in G is non-repetitive, then this proper colouring is said to be a Thue colouring of G (see Alon, Grytczuk, Hauszczak & Riordan, 2002).

The Thue chromatic number of G, denoted $\mathit{\pi }(G)$, is defined as the minimum number of colours required for a Thue colouring of G.

It is known that $\mathit{\pi }(P_1)=1$, $\mathit{\pi }(P_2)=\mathit{\pi }(P_3)=2$ and for $n\ge 4$, $\mathit{\pi }(P_n)=3$. Determining ${\mathit{\pi }}^{\prime }(P_n)$ is a hard problem, hence the problem is very hard for graphs in general.

The following lemma is the motivation for our further discussions in this paper.

Lemma 6.1

Škrabul’áková, in press Up to equivalence, there is exactly one non-repetitive 3-colouring of the cycle $C_{11}$.

In view of this lemma, we restrict our further discussion to the path $P_{11}$. Let the vertices of $P_n$ be labelled from left to right to be $v_1,v_2,v_3,\dots v_{11}$. Recall that the colouring sum of a colouring $\mathcal{S}$ is defined by $\mathit{\omega }(\mathcal{S})=\sum _{i=1}^{k}i\mathit{\theta }(c_i)$. The possible minimum Thue colourings of $P_{11}$ are listed below.

(i)	${\mathcal{S}}_1=(c_1,c_2,c_1,c_3,c_1,c_2,c_3,c_1,c_3,c_2,c_3)$ and $\mathit{\omega }({\mathcal{S}}_1)=22$
(ii)	${\mathcal{S}}_2=(c_1,c_2,c_1,c_3,c_1,c_2,c_3,c_2,c_1,c_2,c_3)$ and $\mathit{\omega }({\mathcal{S}}_2)=21$
(iii)	${\mathcal{S}}_3=(c_1,c_2,c_1,c_3,c_2,c_1,c_2,c_3,c_2,c_1,c_3)$ and $\mathit{\omega }({\mathcal{S}}_3)=21$
(iv)	${\mathcal{S}}_4=(c_1,c_2,c_1,c_3,c_2,c_3,c_1,c_3,c_2,c_1,c_3)$ and $\mathit{\omega }({\mathcal{S}}_4)=22$
(v)	${\mathcal{S}}_5=(c_1,c_2,c_1,c_3,c_1,c_2,c_3,c_1,c_3,c_2,c_1)$ and $\mathit{\omega }({\mathcal{S}}_5)=20$
(vi)	${\mathcal{S}}_6=(c_1,c_2,c_1,c_3,c_2,c_3,c_1,c_3,c_2,c_1,c_2)$ and $\mathit{\omega }({\mathcal{S}}_6)=21$
(vii)	${\mathcal{S}}_7=(c_2,c_1,c_2,c_3,c_2,c_1,c_3,c_2,c_3,c_1,c_3)$ and $\mathit{\omega }({\mathcal{S}}_7)=23$
(viii)	${\mathcal{S}}_8=(c_2,c_1,c_2,c_3,c_2,c_1,c_3,c_1,c_2,c_1,c_3)$ and $\mathit{\omega }({\mathcal{S}}_8)=21$
(ix)	${\mathcal{S}}_9=(c_2,c_1,c_2,c_3,c_1,c_2,c_1,c_3,c_1,c_2,c_3)$ and $\mathit{\omega }({\mathcal{S}}_9)=21$
(x)	${\mathcal{S}}_{10}=(c_2,c_1,c_2,c_3,c_1,c_3,c_2,c_3,c_1,c_2,c_3)$ and $\mathit{\omega }({\mathcal{S}}_{10})=23$
(xi)	${\mathcal{S}}_{11}=(c_2,c_1,c_2,c_3,c_2,c_1,c_3,c_2,c_3,c_1,c_2)$ and $\mathit{\omega }({\mathcal{S}}_{11})=22$
(xii)	${\mathcal{S}}_{12}=(c_2,c_1,c_2,c_3,c_1,c_3,c_2,c_3,c_1,c_2,c_1)$ and $\mathit{\omega }({\mathcal{S}}_{12})=21$
(xiii)	${\mathcal{S}}_{13}=(c_3,c_2,c_3,c_1,c_3,c_2,c_1,c_3,c_1,c_2,c_1)$ and $\mathit{\omega }({\mathcal{S}}_{13})=22$
(xiv)	${\mathcal{S}}_{14}=(c_3,c_2,c_3,c_1,c_3,c_2,c_1,c_2,c_3,c_2,c_1)$ and $\mathit{\omega }({\mathcal{S}}_{14})=23$
(xv)	${\mathcal{S}}_{15}=(c_3,c_2,c_3,c_1,c_2,c_3,c_2,c_1,c_2,c_3,c_1)$ and $\mathit{\omega }({\mathcal{S}}_{15})=23$
(xvi)	${\mathcal{S}}_{16}=(c_3,c_2,c_3,c_1,c_2,c_1,c_3,c_1,c_2,c_3,c_1)$ and $\mathit{\omega }({\mathcal{S}}_{16})=22$
(xvii)	${\mathcal{S}}_{17}=(c_3,c_2,c_3,c_1,c_3,c_2,c_1,c_3,c_1,c_2,c_3)$ and $\mathit{\omega }({\mathcal{S}}_{17})=24$
(xviii)	${\mathcal{S}}_{18}=(c_3,c_2,c_3,c_1,c_2,c_1,c_3,c_1,c_2,c_3,c_2)$ and $\mathit{\omega }({\mathcal{S}}_{18})=23$
(xix)	${\mathcal{S}}_{19}=(c_1,c_3,c_1,c_2,c_1,c_3,c_2,c_1,c_2,c_3,c_2)$ and $\mathit{\omega }({\mathcal{S}}_{19})=21$
(xx)	${\mathcal{S}}_{20}=(c_1,c_3,c_1,c_2,c_1,c_3,c_2,c_3,c_1,c_3,c_2)$ and $\mathit{\omega }({\mathcal{S}}_{20})=22$
(xxi)	${\mathcal{S}}_{21}=(c_1,c_3,c_1,c_2,c_3,c_1,c_3,c_2,c_3,c_1,c_2)$ and $\mathit{\omega }({\mathcal{S}}_{21})=22$
(xxii)	${\mathcal{S}}_{22}=(c_1,c_3,c_1,c_2,c_3,c_2,c_1,c_2,c_3,c_1,c_2)$ and $\mathit{\omega }({\mathcal{S}}_{22})=21$
(xxiii)	${\mathcal{S}}_{23}=(c_1,c_3,c_1,c_2,c_1,c_3,c_2,c_1,c_2,c_3,c_1)$ and $\mathit{\omega }({\mathcal{S}}_{23})=20$
(xxiv)	${\mathcal{S}}_{24}=(c_1,c_3,c_1,c_2,c_3,c_2,c_1,c_2,c_3,c_1,c_3)$ and $\mathit{\omega }({\mathcal{S}}_{24})=22$

From the above list, we note that ${\mathit{\pi }}^{\prime }(P_{11})=20$ and ${\mathit{\pi }}^{+}(P_{11})=24$. We strongly believe that the next conjecture holds.

Conjecture 6.2

For a path $P_n,n\ge 4$, there is a unique permutation over all proper b-colourings for which ${\mathit{\phi }}^{+}(P_n)$ is obtained, and exactly two permutations for which ${\mathit{\phi }}^{\prime }(P_n)$ is obtained.

The following general result is of importance for all variations of colouring sums discussed thus far. It holds for improper colourings as well. A general colouring which meets some general colouring index is called the $\mathit{\vartheta }$-chromatic number of G and denoted, $\mathit{\vartheta }(G)$.

Theorem 6.3

(Makungu’s Theorem¹) If the set of colours $\mathcal{C}=\{c_j:1\le j\le k\}$ allows a general colouring, $\mathcal{S}:f(v_i)=c_l$, $l\in \{1,2,3,\dots ,k\}$ of G, such that $\mathit{\omega }(\mathcal{S})={\mathit{\vartheta }}^{\prime }(G)=min\{\sum _{i=1}^{k}i·\mathit{\theta }(c_i):\forall$$\mathcal{S}$-colourings of $G\}$, then ${\mathit{\vartheta }}^{+}(G)=\sum _{i=1}^{k}i·\mathit{\theta }(c_{(k+1)-i})$.

Proof

Since for $a_1\ge a_2$ it follows that $1·a_1+2·a_2\le 2·a_1+1·a_2$, it follows through immediate induction that if $a_1\ge a_2\ge a_3\ge \cdots \ge a_k$ then for permuted one-on-one allocations of the elements in $b_i\in \{1,2,3,\cdots ,k\}$ to form $\sum _{i=1}^k{a}_i{b}_i$ we have, $min\{\sum _{i=1}^k{a}_i{b}_i\}=\sum _{i=1}^{k}i·a_i$ and $max\{\sum _{i=1}^k{a}_i{b}_i\}=\sum _{i=1}^{k}i·a_{(k+1)-i}$. Hence, if a $\mathit{\vartheta }$-colouring of G is allowed by $\mathcal{C}=\{c_1,c_2,c_3,\dots ,c_k\}$ such that, $\mathit{\theta }(c_1)\ge \mathit{\theta }(c_2)\ge \mathit{\theta }(c_3)\ge \dots \ge \mathit{\theta }(c_k)$ then, ${\mathit{\vartheta }}^{\prime }(G)=\sum _{i=1}^{k}i·\mathit{\theta }(c_i)$ and ${\mathit{\vartheta }}^{+}(G)=\sum _{i=1}^{k}i·\mathit{\theta }(c_{(k+1)-i})$. $\square$

Acknowledgements

The authors gratefully acknowledge the contributions of anonymous referees whose critical and constructive comments played a vital role in improving the quality and presentation style of the paper in a significant way.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

Johan Kok

Johan Kok is registered with the South African Council for Natural Scientific Professions (South Africa) as a professional scientist in both Physical Science and Mathematical Science. His main research areas are in Graph Theory and the reconstruction of motor vehicle collisions.

N.K. Sudev

N.K. Sudev has been working as a Professor (Associate) in the Department of Mathematics, Vidya Academy of Science and Technology, Thrissur, India, for the last fifteen years. His primary research areas are Graph Theory and Combinatorics.

K.P. Chithra

K.P. Chithra is an independent researcher in Mathematics. Her primary research area is also Graph Theory.

Notes

1 The first author dedicates this theorem to Makungu Mathebula and he hopes this young lady will grow up with a deep fondness for mathematics.