# On New Thue Colouring Concepts of Certain Graphs

Johan Kok  Tshwane Metropolitan Police Department
City of Tshwane, Republic of South Africa
<EMAIL_ADDRESS>Erika Škrabul’áková Division of Applied Mathematics
Technical University of Košice
Košice, Slovakia
<EMAIL_ADDRESS>Naduvath Sudev Department of Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur - 680501, India.
<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a simple undirected graph of order $n\geq 1$ and let $\varphi$ be a
proper vertex colouring of $G$. The Thue colouring of a graph is a colouring
such that the sequence of vertex colours of any path of even and finite length
in $G$ is non-repetitive. The change in the Thue number, $\pi(G)$, as edges
are iteratively removed from a graph $G$ is studied. Clearly
$\pi(G-e)\leq\pi(G),~{}e\in E(G)$. As the edges are removed iteratively the
resultant values of $\pi$ are used to construct a Thue sequence for the graph
$G$. The notion of the $\tau$-index denoted, $\tau(G)$, of a graph $G$ is
introduced as well. $\tau(G)$ serves as a measure for the efficiency of edge
deletion to reduce the Thue chromatic number of a graph $G$.

Keywords: Thue chromatic number, Thue number, Thue sequence, $\tau$-index.

AMS Classification Numbers: 05C15, 05C55, 05D40.

##  1 Introduction

For general notation and concepts in graph and digraph theory, we refer to [4,
5, 10, 11, 16]. Unless mentioned otherwise, all graphs we consider in this
paper are simple, connected, finite and undirected graphs.

Recall that two vertices $u$ and $v$ are said to be adjacent if there exist an
edge between them and they are said to be reachable from one to the other if
there exist a finite path between them. In other words, two vertices $u$ and
$v$ is said to be reachable in $G$ if and only if the distance $d_{G}(u,v)$ is
finite, where $d_{G}(u,v)$ is the length of shortest path between the vertices
$u$ and $v$ in $G$. Since a vertex $v$ is inherently adjacent to itself, the
distance $d_{G}(u,u)=0$. Consider the graph $G=G_{1}\cup G_{2}$, the
(disjoint) union of $G_{1}$ and $G_{2}$. Then, the distance between a vertex
$u\in G_{1}$ and a vertex $v\in G_{2}$ is defined to be $d_{G}(u,v)=\infty$.

A finite sequence $S=(q_{1},q_{2},q_{3},\ldots,q_{t})=(q_{i})_{i=1}^{t}$ of
symbols of any alphabet is said to be non-repetitive if for all subsequences
$(r_{1},r_{2},r_{3},\ldots,r_{2m});m\geq 1,2m\leq t$ of symbols, the condition
$r_{i}\neq r_{i+i}$ holds for all $1\leq i\leq m$.

The theory on graph colouring has become a fertile research area since the
second half of nineteenth century. Several types of graph colouring patterns
were introduced and studied over the years. In this paper, we study a
particular type of vertex colouring of graphs, namely Thue Coloring. This type
of graph colouring is named after the Norwegian mathematician Axel Thue, who
introduced the notion of Thue colouring as follows.

######  Definition 1.1.

[15] Let $G$ be a simple undirected graph of order $n\geq 1$ and let $\varphi$
be 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 $\varphi$ is
called a Thue colouring of $G$.

######  Definition 1.2.

[15] The Thue chromatic number of $G$, denoted by $\pi(G)$, is the minimum
number of colours required for a Thue colouring of $G$.

Certain studies on the Thue colouring of graphs have been done in [1, 2, 3, 6,
7, 13, 14]. Motivated by these studies, we introduce new Thue colouring
concepts and study these for of certain graphs.

##  2 Thue Sequence of a Graph

In this section, we first discuss the change in the Thue number, $\pi(G)$, as
edges are iteratively removed from a graph $G$. By definition, we have
$\pi(K_{1})=1$ and if $G=\bigcup_{i=1}^{\ell}G_{i}$, where each $G_{i}$ is a
simple connected graph, then $\pi(G)=\max\\{\pi(G_{i}):1\leq i\leq\ell\\}$.
Clearly, $\pi(G-e)\leq\pi(G),~{}e\in E(G)$. Label the edges of
$G,~{}e_{1},e_{2},e_{3},\ldots,e_{\epsilon}$, where $\epsilon$ is the number
of edges in $G$. Then, we can define a Thue sequence as follows.

######  Definition 2.1.

Let $G=G^{\ast}_{0}$ and $G^{\ast}_{i}=G^{*}_{i-1}-e_{j},e_{j}\in E(G_{i-1})$,
then the sequence $(\pi(G^{*}_{i}))_{1=1}^{\epsilon}$ is called a Thue
sequence of $G$.

The following proposition provides a relation between Thue numbers of a graph
$G$ and that of a graph obtained by joining some of their non-adjacent
vertices.

######  Proposition 2.1.

For a graph $G$, which is not complete, of order $n\geq 3$ we have
$\pi(G)\leq\pi(G+uv);u,v\in V(G)$.

###### Proof.

Recall that $\pi(P_{3})=2$ and $\pi(C_{3})=3$ (see [13, 15]). Hence, the
result holds for non-complete graphs on $3$ vertices. Now, assume that the
results holds for all non-complete graphs $G$ on $4\leq n\leq k$ vertices.
Consider the non-complete graph $H=G\bigcup K_{1}$ on $k+1$ vertices. Now, by
the induction hypothesis, the result $\pi(G)=\pi(G\cup
K_{1})\leq\pi((G+uv)\cup K_{1})$ holds. Hence, we need only to check the cases
by adding the edges $uv_{i}$, where $u$ is the vertex of $K_{1}$ and $v_{i}\in
V(G)$. Add the edge $uv_{i}$. Clearly, by re-colouring, we have either
$\pi(G+uv_{i})=\pi(G)$ or $\pi(G+uv_{i})=\pi(G)+1$. By immediate induction,
the second equation holds for any number of edges $uv_{i},1\leq i\leq k$,
added to $G$ to obtain a new graph $G^{\prime}$. If $G^{\prime}$ is not
complete, then again by induction, it follows that
$\pi(G^{\prime})\leq\pi(G^{\prime}+uv_{j})$ for all possible $v_{j}\in
V(G^{\prime})$. Hence, the result holds for all graphs, that are not complete,
on $k+1$ vertices. Then, the result follows by induction. ∎

######  Proposition 2.2.

For graph $G$ of order $n\geq 1$ we have $\pi(G-e)\leq\pi(G)$ for all $e\in
E(G)$.

###### Proof.

The result follows by similar reasoning used in the proof of Proposition 2.1.
∎

Note that if a graph $G$ is a Hamiltonian graph, then $\pi(G)\geq 3$. Label
the edges of $G$ in injective manner by
$e_{1},e_{2},e_{3},\ldots,e_{\epsilon}$. Also, let $G=G^{\ast}_{0}$ and
$G^{\ast}_{i}=G^{\ast}_{i-1}-e_{j},~{}e_{j}\in E(G_{i-1})$, then the sequence
$(\pi(G^{\ast}_{i})_{1=1}^{\epsilon}$ is called a Thue sequence of the edge
deletion sequence. There are $\epsilon!$ such edge deletion sequences for $G$.
Let $s_{\pi,j}$, for all $1\leq j\leq\epsilon!$ denote the edge deletion
sequences.

######  Definition 2.2.

For an edge deletion sequence $(s_{\pi,j}),j\in\\{1,2,3\ldots,\epsilon!\\}$,
define the $\tau$-index by
$\tau(s_{\pi,j})=\frac{1}{\epsilon+1}\sum\limits_{i=0}^{\epsilon}\pi(G^{\ast}_{i})$.

Invoking the above definition, we can say that the $\tau$-index of a graph $G$
is the efficiency of edge deletion to reduce the Thue chromatic number of $G$.
Hence, the $\tau$-index of a graph $G$ is defined as follows.

######  Definition 2.3.

For a graph $G$ the $\tau$-index of
$G,~{}\tau(G)=\min\\{\tau(s_{\pi,j}):\forall s_{\pi,j},1\leq
j\leq\epsilon\,!\\}$.

######  Illustration 1.

Consider the cycle $C_{9}$ and label the vertices by
$v_{1},v_{2},v_{3},\ldots,v_{9}$ in a clockwise manner and the edges by
$e_{i}=v_{i}v_{i+1}$ in the sense that $v_{n+1}=v_{1}$. Consider the edge
deletion sequence $s_{\pi,1}=(e_{1},e_{2},e_{3},\ldots,e_{9})$. Deleting the
edges sequentially results in the Thue sequence $(4,3,3,3,3,3,3,2,2,1)$.
Hence, $\tau(s_{\pi,1})=\frac{27}{10}$.

Now, consider the edge deletion sequence
$s_{\pi,2}=(e_{3},e_{6},e_{2},e_{4},e_{6},e_{8},e_{1},e_{5},e_{7},e_{9})$. The
corresponding Thue sequence is given by $(4,3,3,2,2,2,2,2,2,1)$. Hence,
$\tau(s_{\pi,2})=\frac{23}{10}$. Over all $s_{\pi,j},~{}1\leq j\leq 9!$ we
find $\tau(C_{9})=\frac{23}{10}$.

######  Corollary 2.3.

For a graph $G,~{}\pi(G)=1$ if and only if $E(G)=\emptyset$. That is, the Thue
chromatic number of a graph $G,$ not necessary connected, is $1$ if and only
if it is an edgeless graph.

###### Proof.

Let $E(G)=\emptyset$. The result is trivially true for $K_{1}$. For an
edgeless graph on $n\geq 2$ vertices the colouring $\varphi:v_{i}\mapsto
c_{1},\forall~{}v_{i}\in V(G)$ is a proper minimum vertex colouring of $G$.
Also, since no distinct vertices of $G$ are reachable,
$\pi(G)=\max\\{\underbrace{\pi(K_{1}),\pi(K_{1}),\ldots\pi(K_{1})}_{n-entries}\\}$
and hence the result holds.

Now, let $\pi(G)=1$ and assume that $G$ has at least one edge say, $uv$. Since
a Thue colouring is a proper vertex colouring $\varphi$ of $G$, the chromatic
number $\chi(G)\geq 2$ and hence $\pi(G)\geq 2$. This is a contradiction to
the hypothesis and therefore $G$ is edgeless. ∎

Since $0!=1$ the edgeless graph has the default edge deletion sequence
$s_{\pi,\emptyset}$. For a trivial graph $G$, it follows from Definitions 2.2
and 2.3 that $\tau(s_{\pi,\emptyset})=\tau(G)=1$.

######  Theorem 2.4.

For all graphs $G$ with $\epsilon\geq 1$, we have
$\frac{3}{2}\leq\min\\{\tau(G)\\}<2$.

###### Proof.

First, note that $\tau(P_{2})=\frac{3}{2}$ and hence we have
$\min\\{\tau(G)\\}\geq\frac{3}{2}$. Also, note that the unique Thue sequence
of the star $K_{1,n}$ is $(\underbrace{2,2,2,\ldots,2}_{n-entries},1)$. Since
$\pi(G^{\ast}_{i})\in\mathbb{N},~{}1\leq i\leq\epsilon(G)$, no other Thue
sequence of any other graph $G$ with $n$ edges can improve on the minimality
of $\tau(K_{1,n})$. Since $\lim_{n\to\infty}\frac{2n+1}{n+1}=2$, the result
$\frac{3}{2}\leq\min\\{\tau(G)\\}<2$ follows. ∎

Observe that for all graphs $G$ with $\epsilon(G)\geq 2$ the inequality
$\tau(S_{1,n})<\tau(G)$ holds.

###  2.1 $\tau$-Index of Paths and Cycles

From [13] it is known that $\pi(P_{1})=1,~{}\pi(P_{2})=\pi(P_{3})=2$ and
$\pi(P_{n})=3$ for $n\geq 4$. Hence, the most efficient way to reduce the Thue
number of paths through edge deletion is to delete edges which create
$P_{1},P_{2},P_{3}$ components. For paths $P_{n},~{}n\geq 4$, the following
result holds.

######  Proposition 2.5.

For a path $P_{n},~{}n\geq 4$, the $\tau$-index is given by

$\tau(P_{n})=\begin{cases}\frac{7n-6}{3n};&n=3t,~{}t\in\mathbb{N},\\\
\frac{7n-5}{3n};&n=3t-1,~{}t\in\mathbb{N},\\\
\frac{7n-4}{3n};&n=3t-2,~{}t\in\mathbb{N}.\end{cases}$

###### Proof.

Consider a path $P_{n},~{}n\geq 4$. Label the vertices and the edges of the
path from left to right, $v_{1},v_{2},v_{3},\ldots,v_{n}$ and
$e_{1},e_{2},e_{3},\ldots,e_{n-1}$, respectively.

Let $n=3t,t\in\mathbb{N}$. First, consider the partial edge deletion sequence
$s_{\pi,1}=(e_{3},e_{6},e_{9},\ldots,e_{3(t-2)})$. Deleting these edges
sequentially results in the partial Thue sequence
$(\underbrace{3,3,3,\ldots,3}_{(t-1)-entries})$. Hence, the partial sum is
equal to $3(t-1)=\frac{3n}{3}-3$.

Now, consider the partial edge deletion sequence
$s_{\pi,2}=(e_{1},e_{4},e_{7},\ldots,e_{3(t-1)})$. Deleting these edges
sequentially results in the partial Thue sequence
$(\underbrace{2,2,2,\ldots,2}_{2t-entries})$. The corresponding partial sum is
equal to $4t=\frac{4n}{3}$. So far, we have deleted $(t-2)+2t=3t-2$ edges.
Deleting the last edge adds the partial sum, by $1$. From Definition 2.2, it
follows that
$\tau(P_{n})=\frac{1}{n}(\frac{3n}{3}-3+\frac{4n}{3}+1)=\frac{7n-6}{3}$.

The other cases will also follow by a similar counting technique. ∎

The result of Proposition 2.5 can be re-written as
$\tau(P_{n})=\frac{1}{n}\left(\frac{7(n+i)}{3}-2(i+1)\right),~{}i\in\\{0,1,2\\}$
and $n=3t-i,~{}t\in\mathbb{N}$. Let $\mathbb{C}=\\{5,7,9,10,14,17\\}$. From
[6], we have $\pi(C_{n})=4,~{}n\in\mathbb{C}$, else $\pi(C_{n})=3$.

######  Proposition 2.6.

Consider a cycle $C_{n},n\geq 4$, then

$\tau(C_{n})=\begin{cases}\frac{7n-i+6}{3(n+1)};&i\in\\{0,1,2\\}~{}~{}\text{and}~{}~{}n=3t-i,~{}t\in\mathbb{N},n\in\mathbb{C},\\\
\frac{7n-i+3}{3(n+1)};&\text{otherwise}.\end{cases}$

###### Proof.

Observe that $C_{n}-e,~{}e\in V(C_{n})$ is the path $P_{n}$, and hence the
result follows immediately. ∎

Observe that for the corresponding line graphs, $\tau(L(P_{n}))=\tau(P_{n-1})$
and $\tau(L(C_{n}))=\tau(C_{n})$. In respect of non-repetitive edge colouring,
the Thue chromatic index or Thue index for brevity, denoted $\pi^{\prime}(G)$
is defined in (see [1]) as a minimal, proper, non-repetitive edge colouring.
Since edge colouring of the edges of a graph $G$ is equivalent to vertex
colouring of the vertices of the line graph $L(G)$, all known results for
$\pi(G),\pi^{\prime}(G)$ and $\tau(G)$ are easily transversable between graphs
and line graphs.

###  2.2 $\tau$-Index of Complete Graphs

It is known that $\pi(K_{n\geq 1})=n$, (see [13]). We now study the
$\tau$-index of complete graphs $K_{n},~{}n\geq 3$. The basis for the proof of
the next result through induction, can be illustrated as follows. Consider the
complete graph $K_{3}$ and label the edges $e_{1},e_{2},e_{3}$. Deleting these
edges sequentially results in the Thue sequence $(3,2,2,1)$. Extend $K_{3}$ to
$K_{4}$ and remove the same edges sequentially. The partial Thue sequence is
now given by $(4,3,3,2)$ and the resultant graph is $K_{1,3}$. Hence, on
deleting $2$ additional edges the partial Thue sequence becomes
$(4,3,3,2,2,2)$. On deleting the last edge, we get the complete Thue sequence
$(4,3,3,2,2,2,1)$.

######  Proposition 2.7.

For $n\geq 2$, the $\tau$-index of a complete graph $K_{n}$ is
$\tau(K_{n})=\frac{2}{n(n-1)}(\sum\limits_{i=0}^{n-2}(i+1)(n-i)+1)$.

###### Proof.

We proceed by mathematical induction. The result trivially holds for $K_{2}$
and $K_{3}$. Now, assume that it holds for $K_{t},~{}2\leq t\leq m$. Hence,
the Thue sequence of $K_{m}$ is given by
$(m,m-1,m-1,m-2,m-2,m-2,\ldots,\underbrace{(m-\ell),(m-\ell)\ldots,(m-\ell)}_{(\ell+1)-entries},\\\
\ldots,\underbrace{2,2,2,\ldots,2}_{(m-1)-entries},1)$.

Now, consider the complete graph $K_{m+1}$ and delete the edges of the
subgraph $K_{m}$ as before and then delete the edges of the resultant graph
$K_{1,m}$. Then, the Thue sequence of $K_{m+1}$ is given by
$(m+1,m,m,(m-1),(m-1),(m-1),\ldots,\underbrace{(m-\ell+1),(m-\ell+1)\ldots,(m-\ell+1)}_{(\ell+1)-entries},\ldots,\underbrace{3,3,3,\ldots,3}_{(m-1)-entries},2,\underbrace{2,2,2\ldots,2}_{(m-1)-entries},1)$.
This sequence can be written as $(q_{i}:(i+1)(n-i),0\leq i\leq n-2)\cup(1)$.
As $\epsilon(K_{m+1})=\frac{m(m+1)}{2}$, we have
$\tau(K_{m+1})=\frac{2}{m(m+1)}\sum\limits_{i=0}^{m-1}(i+1)((m+1)-i)+1)$.

Hence, the result follows by induction. ∎

##  3 Thue Colouring of Linear Jaco Graphs

As a generalisation of certain types of Jaco graphs, the notion of a linear
Jaco graph has been introduced in [12] as follows.

######  Definition 3.1.

[12] Let $f(x)=mx+c;x\in\mathbb{N},~{}m,c\in\mathbb{N}_{0}$. The family of
infinite linear Jaco graphs, denoted by
$\\{J_{\infty}(f(x)):f(x)=mx+c;x\in\mathbb{N}$ and $m,c\in\mathbb{N}_{0}\\}$,
is defined by
$V(J_{\infty}(f(x)))=\\{v_{i}:i\in\mathbb{N}\\},~{}A(J_{\infty}(f(x)))\subseteq\\{(v_{i},v_{j}):i,j\in\mathbb{N},i<j\\}$
and $(v_{i},v_{j})\in A(J_{\infty}(f(x)))$ if and only if
$(f(i)+i)-d^{-}(v_{i})\geq j$.

######  Definition 3.2.

[12] The family of finite linear Jaco graphs denoted by
$\\{J_{n}(f(x)):f(x)=mx+c;x\in\mathbb{N}$ and $m,c\in\mathbb{N}_{0}\\}$ is
defined by $V(J_{n}(f(x)))=\\{v_{i}:i\in\mathbb{N},i\leq
n\\},~{}A(J_{n}(f(x)))\subseteq\\{(v_{i},v_{j}):i,j\in\mathbb{N},i<j\leq n\\}$
and $(v_{i},v_{j})\in A(J_{n}(f(x)))$ if and only if
$(f(i)+i)-d^{-}(v_{i})\geq j$.

A vertex which attains the degree $\Delta(J_{n}(f(x)))$ is called a Jaconian
vertex and the set of Jaconian vertices of the Jaco graph $J_{n}(f(x))$ is
called the Jaconian set of $J_{n}(f(x))$ and is denoted by
$\mathbb{J}(J_{n}(x))$ or simply by $\mathbb{J}_{n}(x)$ for brevity, if the
context is clear. The lowest numbered (subscripted) Jaconian vertex is called
the prime Jaconian vertex of a Jaco Graph.

If $v_{i}$ is the prime Jaconian vertex of a Jaco Graph $J_{n}(1)$, the
complete subgraph on vertices $v_{i+1},v_{i+2},\ldots,v_{n}$ is called the
Hope subgraph or Hope graph of a Jaco Graph and is denoted by
$\mathbb{H}(J_{n}(x))$ or $\mathbb{H}_{n}(x)$ for brevity.

We refer to the corresponding underlying graph of $J_{n}(f(x))$, denoted
$J^{\ast}_{n}(f(x))$, as a Jaco graph as well. We recall a result from [12].

######  Lemma 3.1.

[12] For $m=0$ and $c\geq 0$, two special classes of disconnected linear Jaco
graphs exist. For $c=0$ the Jaco graph $J_{n}(0)$ is a null graph (edgeless
graph) on $n$ vertices. For $c>0$, the Jaco graph
$J_{n}(c)=\bigcup\limits_{\lfloor\frac{n}{c+1}\rfloor-copies}K_{c+1}\bigcup
K_{n-(c+1)\cdot\lfloor\frac{n}{c+1}\rfloor}$.

######  Proposition 3.2.

Let $m=0$ and $c\geq 0$, then $\pi(J^{\ast}_{n\geq
1}(c))\in\\{1,2,3,\ldots,c+1\\}$.

###### Proof.

From Lemma 3.1, it follows that if $c=0$ then $J^{\ast}_{n\geq 1}(0)$ is an
edgeless graph. Hence, $\pi(J^{\ast}_{n\geq 1}(0))=1$. If $c>0$ then
$J^{\ast}_{n\geq 1}(c)$ is the union of complete graphs of which a largest
component is $K_{c+1}$ if and only if $n\geq c+1$. Hence, $\pi(J^{\ast}_{n\geq
c+1}(c))=c+1$. For $t\leq c$ we have a complete graph $K_{t}$ thus,
$\pi(J^{\ast}_{1\leq t\leq c}(c))=t$. This settles the result that
$\pi(J^{\ast}_{n\geq 1}(c))\in\\{1,2,3,\ldots,c+1\\}$. ∎

We now present a corresponding result for the case $m=1,c=0$. First, recall a
lemma from [12].

######  Lemma 3.3.

[12] For a Jaco graph $J^{\ast}_{n+1}(x)$ we have,
$\Delta(J^{\ast}_{n+1}(x))=\Delta(J^{\ast}_{n}(x))$ or
$\Delta(J^{\ast}_{n}(x))+1$.

######  Theorem 3.4.

[Bokang’s theorem111The first author dedicates this theorem to Miss Bokang
Lerato Tshabalala who is expected to grow up with a deep fond of mathematics.]
For the Jaco graph $J^{\ast}_{n}(x),~{}n\geq 1$ we have
$\Delta(J^{\ast}_{n}(x))\leq\pi(J^{\ast}_{n}(x))\leq\Delta(J^{\ast}_{n}(x))+2$.

###### Proof.

For $n=1,2,3,4$ the corresponding Jaco graphs are paths so the result holds.
Since the Hope graph of $J^{\ast}_{n}(x),~{}\forall n\in\mathbb{N}$ is a
complete graph $K_{\Delta(J^{\ast}_{n}(x))}$, the lower bound is obvious. For
$J^{\ast}_{5}(x)$, we have the path $v_{1},v_{2},v_{3},v_{4},v_{5}$ with the
added edge $v_{3}v_{5}$. Clearly,
$\pi(J^{\ast}_{5}(x))=4=\Delta(J^{\ast}_{5}(x))+1$. Assume that it holds for
all Jaco graphs $J^{\ast}_{n}(x),~{}5\leq n\leq k$ and let the vertices of
$J^{\ast}_{k}(x)$ allow the Thue colouring
$\varphi:V(J^{\ast}_{k}(x))\mapsto\\{c_{1},c_{2},c_{3},\ldots,c_{\ell}\\},~{}\ell\leq\Delta(J^{\ast}_{k}(x))+1$
with $\varphi:v_{1}\mapsto c_{1}$. Now, consider $J^{\ast}_{k+1}(x)$. Since
$\Delta(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k}(x))$ or
$\Delta(J^{\ast}_{k}(x))+1$ and $\pi(J^{\ast}_{k}(x))=\Delta(J^{\ast}_{k}(x))$
or $\Delta(J^{\ast}_{k}(x))+1$, we consider the following four cases. Let
$\varphi=\varphi^{\prime}$ for $v_{i},1\leq i\leq k$ and
$\varphi^{\prime}:v_{k+1}\mapsto c_{\ell+1}$.

Case 1: Let $\ell=\pi(J^{\ast}_{k}(x))=\Delta(J^{\ast}_{K}(x))$;
$\Delta(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k}(x))$. Since
$\varphi^{\prime}:v_{k+1}\mapsto c_{\ell+1}$ might not allow a minimum Thue
colouring, $\pi(J^{\ast}_{k+1}(x))\leq\Delta(J^{\ast}_{k+1}(x))+1$.

Case 2: Let $\ell=\pi(J^{\ast}_{k}(x))=\Delta(J^{\ast}_{K}(x))$;
$\Delta(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k}(x))+1$. Since
$\Delta(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k}(x))+1$, the colouring
$\varphi^{\prime}:v_{k+1}\mapsto c_{\ell+1}$ allows a minimum Thue colouring
so $\pi(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k+1}(x))+1$.

Case 3: Let $\ell=\pi(J^{\ast}_{k}(x))=\Delta(J^{\ast}_{k}(x))+1$;
$\Delta(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k}(x))+1$. Since
$\varphi^{\prime}:v_{k+1}\mapsto c_{\ell+1}$ might not allow a minimum Thue
colouring, $\pi(J^{\ast}_{k+1}(x))\leq\Delta(J^{\ast}_{k+1}(x))+1$.

Case 4: Let $\ell=\pi(J^{\ast}_{k}(x))=\Delta(J^{\ast}_{k}(x))+1$;
$\Delta(J^{\ast}_{k+1}(x))=\Delta(J^{\ast}_{k}(x))$. The smallest Jaco graph
for which we have this case is $J^{\ast}_{5}(x)$ and $J^{\ast}_{6}(x)$. For
$\varphi^{\prime}:v_{1}\mapsto c_{1},\varphi^{\prime}:v_{2}\mapsto
c_{2},\varphi^{\prime}:v_{3}\mapsto c_{1},\varphi^{\prime}:v_{4}\mapsto
c_{3},\varphi^{\prime}:v_{5}\mapsto c_{4},\varphi^{\prime}:v_{6}\mapsto
c_{1}$, a minimum Thue colouring is allowed and
$\pi(J^{\ast}_{6}(x))\leq\Delta(J^{\ast}_{6}(x))+1$. Extend $\varphi^{\prime}$
to $J^{\ast}_{k+1}(x)$ with $\varphi^{\prime}:v_{k+1}\mapsto c_{1}$. Without
loss of generality, assume that there exists a path beginning at vertex
$v_{k+1}$ which represents at least a two block repetitive sequence say,
$(c_{1},c_{j},c_{k},c_{m},\ldots,c_{t},c_{1},c_{j},c_{k},c_{m},\ldots,c_{t})$,
then $(c_{j},c_{k},c_{m},\ldots,c_{t},c_{j},c_{k},c_{m},\ldots,c_{t})$
corresponds to a two block repetitive sequence in $J^{\ast}_{k}(x)$ which is a
contradiction. Equally so, if a two block repetitive sequence
$(c_{j},c_{k},c_{m},\ldots,c_{t},c_{1},c_{j},c_{k},c_{m},\ldots,c_{t},c_{1})$,
then $(c_{j},c_{k},c_{m},\ldots,c_{t},c_{j},c_{k},c_{m},\ldots,c_{t})$
corresponds to a two block repetitive sequence in $J^{\ast}_{k}(x)$, which is
a contradiction. Hence, by induction, it follows that no such repetitive
sequence of any number of blocks exists.

Therefore,
$\Delta(J^{\ast}_{n}(x))\leq\pi(J^{\ast}_{n}(x))\leq\Delta(J^{\ast}_{n}(x))+1$.
∎

We strongly believed that a generalisation of Theorem 3.4 is possible as
provided in the following conjecture.

######  Conjecture 1.

For the Jaco graph $J^{\ast}_{n}(f(x)),~{}f(x)=mx+c,x\in\mathbb{N},~{}m\geq
2,~{}c\geq 1$, we have
$\pi(J^{\ast}_{n}(f(x)))\leq\Delta(J^{\ast}_{n}(f(x)))+\delta(J^{\ast}_{n}(f(x)))$.

##  4 On Thue Distance, Thue Diameter, Thue Radius and Thue Reach

A Thue colouring of a graph $G$ has the property that it is a proper vertex
colouring for which any path in $G$ is a non-repetitive sequence of colours.
Therefore, the property of minimality per se is not embedded in the concept of
a Thue colouring. Hence, a rainbow colouring is a Thue colouring, but not a
minimum Thue colouring. We call a minimum Thue colouring of $G$ a
$\mathfrak{T}$-colouring of $G$.

Hence, if $G$ and $\pi(G)$ are known, and a finite number $t$ colours may be
chosen from then, $\binom{t}{\pi(G)}$ sets of colours are available to choose
from. Call these sets, $\mathfrak{T}$-sets. For any $\mathfrak{T}$-set
different mappings $\varphi_{1},\varphi_{2},\ldots,\varphi_{k}$ exist, all of
which will ensure a minimum Thue colouring of $G$. So for a chosen
$\mathfrak{T}$-set it is true that up to equivalence the many other
$\mathfrak{T}$-sets become irrelevant. Consider a graph $G$ of order $n$ and a
corresponding $\mathfrak{T}$-colouring.

######  Definition 4.1.

For a graph $G$ with $\pi(G)<n$ and a colour $c_{i}$, the Thue colour
distance, denoted by $\pi_{d}(c_{i})$, is defined to be
$\pi_{d}(c_{i})=\min\\{d_{G}(u,v):u,v\in V(G),\varphi(u)=\varphi(v)=c_{i}\\}$.

######  Definition 4.2.

For a graph $G$ with $\pi(G)<n$, the Thue radius of a graph $G$, denoted by
$\pi_{r}(G)$, is defined to be
$\pi_{r}(G)=\min\\{\pi_{d}(c_{i}):\forall\varphi,~{}\forall\pi_{d}(c_{i})>0\\}$.

######  Definition 4.3.

For a graph $G$ with $\pi(G)<n$ and a colour $c_{i}$, the Thue colour
diameter, denoted by $\pi_{D}(c_{i})$, and is defined as
$\pi_{D}(c_{i})=\max\\{d_{G}(u,v):u,v\in V(G),\varphi(u)=\varphi(v)=c_{i}\\}$.

######  Definition 4.4.

For a graph $G$ with $\pi(G)<n$, the Thue reach of a graph $G$, denoted by
$\pi_{R}(G)$, is defined to be $\pi_{R}(G)=\max\\{\pi_{D}(c_{i})\\}$, for all
$\varphi$ and for all $\pi_{D}(c_{i})>0\\}$.

In view of the property of inherent adjacency, we can define the default value
$\pi_{d}(c_{i})=\pi_{D}(c_{i})=0$ for a rainbow colouring. Obviously,
$\pi_{d}(c_{i})\neq 1$ and hence $\pi_{D}(c_{i})\neq 1$.

######  Illustration 2.

To ensure a $\mathfrak{T}$-colouring of $P_{4}$, let the colours to be
$\mathcal{C}=\\{c_{1},c_{2},c_{3}\\}$. There are many possible colourings
($\varphi$’s). Six correspond to $\pi_{d}(c_{i})>0$ for any $i\in\\{1,2,3\\}$.

  1. (i)

$\varphi(v_{1})=c_{1},\varphi(v_{2})=c_{2},\varphi(v_{3})=c_{1},\varphi(v_{4})=c_{3}$.

  2. (ii)

$\varphi(v_{1})=c_{1},\varphi(v_{2})=c_{3},\varphi(v_{3})=c_{1},\varphi(v_{4})=c_{2}$.

  3. (iii)

$\varphi(v_{1})=c_{2},\varphi(v_{2})=c_{1},\varphi(v_{3})=c_{2},\varphi(v_{4})=c_{3}$.

  4. (iv)

$\varphi(v_{1})=c_{2},\varphi(v_{2})=c_{3},\varphi(v_{3})=c_{2},\varphi(v_{4})=c_{1}$.

  5. (v)

$\varphi(v_{1})=c_{3},\varphi(v_{2})=c_{1},\varphi(v_{3})=c_{3},\varphi(v_{4})=c_{2}$.

  6. (vi)

$\varphi(v_{1})=c_{3},\varphi(v_{2})=c_{2},\varphi(v_{3})=c_{3},\varphi(v_{4})=c_{1}$.

For (i), $\pi_{d}(c_{1})=2,~{}\pi_{d}(c_{2})=0,~{}\pi_{d}(c_{3})=0$. Hence
$\pi_{r}(P_{4})=2$. Similarly, for (ii), (iii), (iv), (v), (vi), $\pi_{r}(G)$
is constant regardless of $\varphi$.

Similarly, to ensure the same $\mathfrak{T}$-colouring of $P_{4}$ determines
$\pi_{R}(P_{4})$, consider the following.

  1. (i)

$\varphi(v_{1})=c_{1},\varphi(v_{2})=c_{2},\varphi(v_{3})=c_{3},\varphi(v_{4})=c_{1}$.

  2. (ii)

$\varphi(v_{1})=c_{1},\varphi(v_{2})=c_{3},\varphi(v_{3})=c_{2},\varphi(v_{4})=c_{1}$.

  3. (iii)

$\varphi(v_{1})=c_{2},\varphi(v_{2})=c_{1},\varphi(v_{3})=c_{3},\varphi(v_{4})=c_{2}$.

  4. (iv)

$\varphi(v_{1})=c_{2},\varphi(v_{2})=c_{3},\varphi(v_{3})=c_{1},\varphi(v_{4})=c_{2}$.

  5. (v)

$\varphi(v_{1})=c_{3},\varphi(v_{2})=c_{1},\varphi(v_{3})=c_{2},\varphi(v_{4})=c_{3}$.

  6. (vi)

$\varphi(v_{1})=c_{3},\varphi(v_{2})=c_{2},\varphi(v_{3})=c_{1},\varphi(v_{4})=c_{3}$.

For (i), $\pi_{D}(c_{1})=3,~{}\pi_{D}(c_{2})=0,~{}\pi_{D}(c_{3})=0$, hence
$\pi_{R}(P_{4})=3$. Similarly, for (ii), (iii), (iv), (v), (vi), $\pi_{R}(G)$
is constant regardless of $\varphi$. ∎

These concepts can find application if different colours represent different
technologies to be installed at the points of a network and there is a
requirement that a set of a particular technology should be minimum distance
or maximum distance apart. For example, certain communication technology is
such that the efficiency deteriorates if units are to far apart and a maximum
distance criteria is set. On the other hand, for certain nuclear technology a
minimum distance criteria is set. The next lemma is perhaps obvious but useful
for further results.

######  Lemma 4.1.

A graph $G$ of order $n\geq 3$ is a non-complete graph if and only if a subset
of three vertices say, $\\{u,v,w\\}$ exists such that the induced subgraph
$\langle u,v,w\rangle\neq C_{3}$.

###### Proof.

Since a disconnected graph cannot be complete the result holds for
disconnected graphs. Assume that $G$ is connected.

First, assume that there exist three vertices $v,u,w$ such that $\langle
v,u,w\rangle\neq C_{3}$ then at least $vu\notin E(G)$ or $vw\notin E(G)$ or
$uw\notin E(G)$ so $G$ is not complete.

Conversely, assume that $G$ is a non-complete graph. For any two vertices
$v,w$ for which the edge $vw\notin E(G)$, consider the shortest path
$P=vu_{1}u_{2}u_{3}\ldots u_{k}w$. If $w=u_{2}$, then $\langle
v,u_{1},u_{2}\rangle\neq C_{3}$ and the result follows. However if $u_{2}\neq
w$, then the edge $vu_{2}\notin E(G)$ else the path
$P^{\prime}=vu_{2}u_{3}\ldots w$ is a shortest path which is a contradiction.
Hence, the induced subgraph $\langle v,u_{1},u_{2}\rangle\neq C_{3}$. ∎

In view of the above results, the existence of Thue colouring for graphs, that
are not complete, is discussed in the following theorem.

######  Theorem 4.2.

For a graph $G\neq K_{n},~{}\pi_{r}(G)=2$. In other words, for a graph $G\neq
K_{n}$ there exists a $\mathfrak{T}$-colouring $\varphi$ such that, vertices
$u,v$ exist such that $\varphi(u)=\varphi(v)$ and $d_{G}(u,v)=2$.

###### Proof.

Consider a graph $G\neq K_{n}$ and a corresponding $\mathfrak{T}$-colouring
$\varphi:V(G)\rightarrow\mathcal{C},~{}\mathcal{C}=\\{c_{i}:1\leq
i\leq\pi(G)\\}$ of $G$. Since $G$ is connected, it has $|V(G)|\geq 3$ and at
least one subgraph, $P_{3}$ (see Lemma 4.1). Let $P_{3}=v_{1}v_{2}v_{3}$. If
$\varphi(v_{1})=\varphi(v_{3})$ the result follows. Else, assume without loss
of generality that
$\varphi(v_{1})=c_{1},~{}\varphi(v_{2})=c_{2},~{}\varphi(v_{3})=c_{3}$.
Consider the graph $G-v_{2}$. Hence, if need be, through colour index rotation
it is possible to Thue colour (not necessary minimum) the vertices of
$G-v_{2}$ such that $\varphi(v_{1})=c_{1}$ and $\varphi(v_{3})=c_{1}$ and
$\varphi:v_{j}\mapsto c_{k},~{}c_{k}\in\\{c_{i}:1\leq i\leq\pi(G)\\},~{}j\neq
1,3$. This allows a $\mathfrak{T}$-colouring of $G$ such that
$\pi_{d}(c_{1})=\min\\{d_{G}(u,v):u,v\in
V(G),\varphi(u)=\varphi(v)=c_{1}\\}=d_{G}(v_{1},v_{3})=2$. Therefore,
$\pi_{r}(G)=2$. ∎

It can be noted that the above theorem can be generelised for any graph $G$ as
$\pi_{r}(G)\in\\{0,2\\}$.

###  4.1 On $\pi_{R}(G)$

Observe that for any non-complete graph $G,~{}\pi_{R}(G)\leq diam(G)$. It then
follows that $\pi_{R}(G+e)\leq\pi_{R}(G)$. Except for $K_{n}$ for which
$\pi_{R}(K_{n})=0<1=diam(K_{n})$ no other graphs have been found as yet for
which inequality holds. Hence, it is strongly suspected that
$\pi_{R}(G)=diam(G)$. A proof of the latter still escapes us. We shall
determine $\pi_{R}(G)$ for some classes of graphs.

######  Proposition 4.3.

  1. (i)

For $n\geq 3$, we have $\pi_{R}(P_{n})=diam(P_{n})=n-1$.

  2. (ii)

For $n\geq 4$, we have $\pi_{R}(C_{n})=diam(C_{n})=\lfloor\frac{n}{2}\rfloor$.

  3. (iii)

For a star $S_{n+1},~{}n\geq 2$, we have $\pi_{R}(S_{n+1})=diam(S_{n+1})=2$.

###### Proof.

Part-(i): Without loss of generality let $P_{n}=v_{1}v_{2}v_{3}\ldots v_{n}$
and let $\varphi(v_{1})=c_{1}$ and $c_{i}\in\\{c_{1},c_{2},c_{3}\\}$. Up to
equivalence the path $P_{3}$ has a unique $\mathfrak{T}$-colouring,
$\varphi(v_{1})=c_{1},\varphi(v_{2})=c_{2},\varphi(v_{3})=c_{1}$ hence,
$\pi_{R}(P_{3})=diam(P_{3})=2=3-1$. Assume that the result holds for
$P_{n},~{}3\leq n\leq k$. It implies that $\varphi(v_{k})=c_{1}$ in $P_{k}$.
Consider a $\mathfrak{T}$-colouring of the path $P_{k-1}$ such that
$\varphi(v_{k-1})=c_{1}$ which is possible by the induction assumption. It
implies that $\varphi(v_{k-2})\in\\{c_{2},c_{3}\\}$. Colour
$\varphi(v_{k+1})=c_{1}$ and $\varphi(v_{k})\neq\varphi(v_{k-2})$. Hence, a
$\mathfrak{T}$-colouring of $P_{k+1}$ exists such that
$\pi_{R}(P_{k+1})=diam(P_{k+1})=k$. Therefore, the result is settled through
induction.

Part (ii)(a): Consider two copies of path $P_{n},~{}n\geq 3$ and label them
$P^{\prime}_{n},~{}P^{\prime\prime}_{n}$ respectively. Let
$\mathcal{C}^{\prime}=\\{c_{1},c_{2},c_{3}\\}$ and
$\mathcal{C}^{\prime\prime}=\\{c_{1},c^{\prime}_{2},c^{\prime}_{3}\\}$ allow a
$\mathfrak{T}$-colouring of $P^{\prime}_{n},~{}P^{\prime\prime}_{n}$
respectively such that the four end vertices carry the colour $c_{1}$. From
Part (i) the latter is always possible. Merge the end vertices pairwise (one
each from a different path) to obtain the cycle $C_{2(n-1)}$. Certainly the
cycle has been Thue coloured. Recolour the remaining vertices from say
$P^{\prime\prime}_{n}$ to obtain a $\mathfrak{T}$-colouring for $C_{2(n-1)}$
which is always possible. It follows that $\pi_{D}(c_{1})=n-1$ which is a
maximum over all colours. Hence,
$\pi_{R}(C_{2(n-1)})=diam(C_{2(n-1)})=\frac{2(n-1)}{2}=\lfloor\frac{2(n-1)}{2}\rfloor=n-1$.

Part (ii)(b): Consider two copies of path $P_{n},~{}n\geq 3$ and label them
$P^{\prime}_{n},~{}P^{\prime\prime}_{n}$ respectively. Let
$\mathcal{C}^{\prime}=\\{c_{1},c_{2},c_{3}\\}$ and
$\mathcal{C}^{\prime\prime}=\\{c_{1},c^{\prime}_{2},c^{\prime}_{3}\\}$ allow a
$\mathfrak{T}$-colouring of $P^{\prime}_{n},~{}P^{\prime\prime}_{n}$
respectively such that three end vertices carry the colour $c_{1}$ and one end
vertex from say $P^{\prime\prime}_{n}$ carry the colour $c^{\prime}_{2}$.
Merge one end vertex from $P^{\prime}_{n}$ and one from $P^{\prime\prime}_{n}$
which carries the colour $c_{1}$. Add an edge to join the remaining two end
vertices. Clearly the cycle $C_{2n-1}$ has been Thue coloured. Recolour the
remaining vertices of say $P^{\prime\prime}_{n}$ to obtain a
$\mathfrak{T}$-colouring for $C_{2n-1}$. It follows that $\pi_{D}(c_{1})=n-1$
which is a maximum over all colours. Hence,
$\pi_{R}(C_{2n-1})=diam(C_{2n-1})=\lfloor\frac{2n-1}{2}\rfloor$.
Finally, since any cycle $C_{n},~{}n\geq 4$ can be constructed from either
Parts (ii)(a) or (ii)(b), the result follows.
Part (iii): For $n=2$ the star $S_{2+1}\simeq P_{3}$ so the result follows
from Part (i). Consider $n\geq 3$. Since it trivially holds for $S_{3+1}$ the
result follows through immediate induction. ∎

###  4.2 On Subdivisions of a Graph

For a graph $G$ of order $n$ and vertices $v_{1},v_{2},v_{3},\ldots,v_{n}$, a
$k$-subdivision is obtained by inserting $k$ additional vertices
$u_{\ell},~{}1\leq\ell\leq k$ to each edge $v_{i}v_{j}\in E(G)$. In other
words each edge $v_{i}v_{j}$ is replaced by the path
$v_{i}u_{1}u_{1}u_{3}\ldots u_{k}v_{j}$. Denote the subdivision of $G$ by
$G_{k}$.

The second subdivision is called the cycle subdivision. A distinct pair of
vertices $u,w\in V(C_{m})$ with $d_{C_{m}}(u,w)=diam(C_{m})$, is called
diameter vertices of the cycle $C_{m}$. A cycle subdivision of a graph $G$ is
the graph obtained by inserting a cycle $C_{m}$ into each edge with the edges
$v_{i}u$ and $v_{j}w$, replacing the edge $v_{i}v_{j}$ and vertices $u,w$ are
diameter vertices of $C_{m}$. Denote a cycle subdivision of $G$ by $G_{\circ
m}$.

######  Theorem 4.4.

For a graph $G$ we have

  1. (i)

$\pi(G_{k})\leq\pi(G)+1$, for $k\geq 3$.

  2. (ii)

$\pi(G_{\circ m})\leq\pi(G)+2$, for $m\in\\{5,7,9,10,14,17\\}$ else,
$\pi(G_{\circ m})\leq\pi(G)+1$.

###### Proof.

Part (i): Let a $\mathfrak{T}$-colouring of $G$ be allowed by
$\mathcal{C}=\\{c_{1},c_{2},c_{3},\ldots,c_{\pi(G)}\\}$ and let a
$\mathfrak{T}$-colouring of $P_{k},~{}k\geq 3$ be allowed by
$\mathcal{C}^{\prime}=\\{c^{\prime}_{1},c^{\prime}_{2},c^{\prime}_{3}\\}$ such
that $\mathcal{C}\cap\mathcal{C}^{\prime}=\emptyset$. Consider the subdivision
$G_{k}$ with the initial colouring $\mathcal{C}\cup\mathcal{C}^{\prime}$. For
each edge $v_{i}v_{j}\in E(G)$ recolour the corresponding vertices of the path
which carry the colour $\varphi^{\prime}(u_{1})$ to the colour
$\varphi(v_{j})$. Similarly recolour the corresponding vertices of the path
which carry the colour $\varphi^{\prime}(u_{k})$ to the colour
$\varphi(v_{i})$. Clearly the new colouring is a Thue colouring, perhaps not
minimum. Exactly one new colour $c^{\prime}_{i}\in\mathcal{C}^{\prime}$ has
been added to the initial Thue colouring of $G$ to Thue colour $G_{k}$.
Therefore, for $k\geq 3,~{}\pi(G_{k})\leq\pi(G)+1$.

Part (ii): The second part can also be proved using the similar reasoning as
in Part (i). ∎

Note that in the construction of the cycle subdivision there is no necessity
to link the diameter vertices. The results holds for any distinct pair of
vertices $u_{i},u_{j}\in V(C_{m})$ if $d_{C_{m}}(u_{i},u_{j})\geq 2$.

######  Corollary 4.5.

Consider paths $P_{t},~{}t\in\\{3,4,5,\ldots,k\\}$ and insert any path $P_{t}$
into an edge of $G$. The varied subdivision is denoted $G_{k^{\ast}}$. For
$k\geq 3$ we have $\pi(G_{k^{\ast}})\leq\pi(G)+1$.

######  Corollary 4.6.

Consider cycles $C_{t},~{}t\in\\{3,4,5,\ldots,m\\}$ and insert any cycle
$C_{t}$ into an edge of $G$. The varied subdivision is denoted $G_{\circ
m^{\ast}}$. For $m\in\\{5,7,9,10,14,17\\}$ we have $\pi(G_{\circ
m^{\ast}})\leq\pi(G)+2$ else, $\pi(G_{\circ m^{\ast}})\leq\pi(G)+1$.

The above leads to a general result. We begin by defining the $H$-subdivision
of a given graph $G$.

######  Definition 4.5.

Let the graph $H$ have at least one distinct pair of vertices $u,w$ such that
$d_{H}(u,w)\geq 2$. The $H$-subdivision of a graph $G$, denoted $G_{H}$, is
the graph obtained by inserting the graph $H$ into each edge $v_{i}v_{j}\in
E(G)$ with the edges $v_{i}u$ and $v_{j}w$ replacing the edge $v_{i}v_{j}$.

The following theorem establishes the relation between the Thue chromatic
numbers of the graphs $G$ and $H$ and the $H$-subdivision $G_{H}$ of $G$.

######  Theorem 4.7.

Let $H$ be a graph with at least two distinct vertices $u,w,~{}d_{H}(u,w)\geq
2$. Then, for a graph $G$ we have $\pi(G_{H})\leq\pi(G)+\pi(H)-1$.

###### Proof.

Let a $\mathfrak{T}$-colouring of $G$ be allowed by
$\mathcal{C}=\\{c_{1},c_{2},c_{3},\ldots,c_{\pi(G)}\\}$ and let a
$\mathfrak{T}$-colouring of $H$ be allowed by
$\mathcal{C}^{\prime}=\\{c^{\prime}_{1},c^{\prime}_{2},c^{\prime}_{3}\ldots,c_{\pi(H)}\\}$
such that $\mathcal{C}\cap\mathcal{C}^{\prime}=\emptyset$. Consider the
$H$-subdivision $G_{H}$ with the initial colouring
$\mathcal{C}\cup\mathcal{C}^{\prime}$. For each edge $v_{i}v_{j}\in E(G)$
recolour the corresponding vertices of H which carry the colour
$\varphi^{\prime}(u)$ to the colour $\varphi(v_{j})$. Similarly recolour the
corresponding vertices of $H$ which carry the colour $\varphi^{\prime}(w)$ to
the colour $\varphi(v_{i})$. Clearly the new colouring is a Thue colouring,
perhaps not minimum. Thus far, at most two new colours
$c^{\prime}_{\ell},c^{\prime}_{\ell^{\prime}}\in\mathcal{C}^{\prime}$ have
been removed from the initial Thue colouring of $G_{H}$. Since this new Thue
colouring might not be minimum, $\pi(G_{H})\leq\pi(G)+\pi(H)-1$. ∎

##  5 Conclusion

So far, we have discussed the Thue colouring of certain graph classes and
studied certain parameters of certain graphs, with respect to this type of
graph colouring. There are so many open problems in this for further
investigations.

Since a closed formula for the number of edges of $J^{\ast}_{n}(f(x))$ is not
known yet, a closed formula for $\tau(J^{\ast}_{n}(f(x)))$ also remains open.
Using the results on determining the number of edges, provided in [12],
$\tau$-index can be determined recursively. The factor
$\sum\limits_{i=0}^{\epsilon(J^{\ast}_{n}(x))}\pi(J^{\ast}_{n,_{i}})$ is edge
dependent as well. Hence, it is desirable to seek a recursive formula for the
aforesaid factor, in the absence of a closed formula for the number of edges
of a Jaco graph. It is believed that a clear understanding of the Thue number
and Thue sequence of caterpillar graphs will be the foundation for finding
such a recursive formula. Other Thue related invariants in respect of Jaco
graphs deserve intensive further investigations.

Certainly the new notions such as Thue sequence, $\tau$-index, Thue distance,
Thue diameter, Thue radius and Thue reach, also offer a wide scope of further
studies.

## References

  * [1] N. Alon, J. Grytczuk, M. Haluszczak, O. Riordan, Non-repetitive colorings of graphs, Random Struct. Algor., 21(3-4)(2002), 336-346, DOI:10.1002/rsa.10057.
  * [2] J. Barát, J. Czap, Facial non-repetitive vertex coloring of plane graphs. J. Graph Theory, 74(1)(2013), 115-121, DOI:10.1002/jgt.21695.
  * [3] J. Barát, D. Wood, Notes on non-repetitive graph colouring, Electron. J. Combin., 15(1)(2008), # R99.
  * [4] J. A. Bondy and U.S.R. Murty, Graph theory with applications, Macmillan Press, London, 1976.
  * [5] G. Chartrand and L. Lesniak, Graphs and digraphs, CRC Press., 2000.
  * [6] J. D. Currie, There are ternary circular square-free words of length n for $n\geq 18$, Electron. J. Combin., 9(2002),1-7.
  * [7] J. Grytczuk, Non-repetitive colorings of graphs: A survey, Int. J. Math. Math. Sci., (2007), 1-10., DOI:10.1155/2007/74639.
  * [8] J. Grytczuk, Thue type problems for graphs, points, and numbers, Discrete Math., 308(19)(2008), 4419–4429, DOI:10.1016/j.disc.2007.08.039
  * [9] J. Grytczuk, J. Kozik, P. Micek, New approach to non-repetitive sequences. Random Struct. Algor., 42(2)(2013), 214–225, DOI: 10.1002/rsa.20411.
  * [10] F. Harary, Graph theory, Addison Wesley, 1969.
  * [11] J. B. Jensen and G. Gutin, Digraphs: Theory, algorithms and applications, Springer-Verlag., 2007.
  * [12] J. Kok, C. Susanth and S.J. Kalayathankal, A study on linear Jaco graphs, J. Inform. Math. Sci., 7(2)(2015), 69-80.
  * [13] E. Škrabul’áková, Thue choice number versus Thue chromatic number of graphs, Pre-print, arXiv: 1508.02559v1.
  * [14] J. Schreyer and E. Škrabul’áková, Total Thue colouring of graphs, European J. Math. 1(1)(2015), 186–197, DOI:10.1007/s40879-014-0016-2.
  * [15] A. Thue, Über unendliche Zeichenreihen, Norske Videnskabers Selskabs Skrifter, I Mathematisch-Naturwissenschaftliche Klasse, Christiania, 7(1906), 1–22.
  * [16] D. B. West, Introduction to graph theory, Pearson Education Inc., 2001.