on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family


CAUCHY –Jurnal Matematika Murni dan Aplikasi 
Volume 7(3) (2022), Pages 432-444 
p-ISSN: 2086-0382; e-ISSN: 2477-3344 

Submitted: June 07, 2022 Reviewed: July 24, 2022 Accepted: August 13, 2022 
DOI: http://dx.doi.org/10.18860/ca.v7i3.16334        

on Graceful Chromatic Number of Vertex amalgamation of Tree 
Graph Family 

Arika Indah Kristiana*, Ahmad Aji , Edy Wihardjo, Deddy Setyawan   

Mathematics Education Department, Jember University of Jember, Indonesia 
  

Email: arika.fkip@unej.ac.id 

ABSTRACT  

Definition graceful k-coloring of graph 𝐺 = (𝑉,𝐸) is proper vertex coloring 𝑐:𝑉(𝐺) →

{1,2,…,𝑘);𝑘 ≥ 2, which induces a proper edge coloring 𝑐′:𝐸(𝐺) → {1,2,…,𝑘 − 1} defined 

𝑐′ (𝑢𝑣) = |𝑐(𝑢) − 𝑐(𝑣)|. The minimum vertex coloring from graph 𝐺 can be colored with graceful 
coloring called a graceful chromatic number with notation 𝜒𝑔 (𝐺). The method used in this 

research is the axiomatic deductive method and pattern recognition. The detection method finds 
coloring patterns and graceful chromatic numbers based on the amalgamation operation of point 
family tree graphs. In this paper, we have investigated the graceful chromatic number of vertex 
amalgamation of tree graph family: path graph, centipede graph, broom, and E graph. The results 
of this study are expected to be used as a basis for studies in developing science and applications 
related to graceful chromatic numbers on the results of point amalgamation operations in tree 
family graphs. 

Keywords: graceful coloring; tree graph family; graceful chromatic number; vertex 
amalgamation. 

INTRODUCTION 

Graceful coloring is the topic of vertex coloring used in this research. Vertex coloring 
is the assignment of color to a vertex where each neighboring vertex is assigned a different 
color [1][2][3]. Graceful coloring is the coloring of each point that induces the coloring of 
each sedge by calculating the difference between two neighboring points [4]. The 
minimum number of colors used in the vertex coloring of graph G is referred to as the 
chromatic numbers in the graceful coloring of G, which is denoted by 𝜒𝑔(𝐺). 

Research on the chromatic number on graceful coloring has been done before. In 
2016, Zhang [4] investigated the graceful coloring of path, wheel, complete bipartite, and 
circle graphs. In 2017, English et. al [5] studied graceful chromatic numbers in tree graphs. 
Furthermore, in 2019, Mincu et al [6] investigated the graceful coloring of 13 graphs 
goldner-harary, fritsch, friendship, fan, wagner, Petersen, house prism, octahedron, 
jellyfish, umbrella, spindle, and diamond graphs. In the same year, Alfarisi et al [7] studied 
graceful coloring on pan, tadpole, and sun graphs. In 2020, Sania et al [8] studied graceful 
staining on a family of uncyclic graphs consisting of bull, cricket, caveman, peach, and 
flowerpot graphs. Furthermore, in 2021, Khoirunnisa et al  [9] continued their research 
with the same topic, but the graph used was the graph of the results of the comb operation. 

http://dx.doi.org/10.18860/ca.v7i3.16334
mailto:arika.fkip@unej.ac.id


on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 433 

The graph that results from the comb operation is a ladder graph with a first-degree path 
and a ladder graph with a circle. Based on this description, research was conducted to find 
a particular graph's graceful chromatic number. The graph that will be studied is the 
result of vertex amalgamation operations in the tree graph family. The family of tree 
graphs used is path graphs, centipedes, brooms, and 𝐸. 

This research will use a point amalgamation operation. The vertex amalgamation 
operation is the acquisition of a new graph from several graphs shown by attaching it to 
the point that has been selected, which is called a terminal point [10][11][12][13]. The 
reason for choosing the vertex amalgamation operation is that the basic graph 
arrangement of the vertex amalgamation cannot change when it is operated compared to 
the edge amalgamation operation, so the colouring pattern used is no different from the 
base graph [14]. 

This article aims to obtain the of a vertex amalgamation of a tree graph family. A tree 
graph family is a graph that has the same properties as a tree graph. For example, a 
connected graph with no circuits is called a tree graph [15]. If graph G has the same 
starting and ending points, then the graph is a circuit graph. Path graph, sweep graph, 
centipede graph, and graph E are some examples of tree graphs [16][17][18]. 

In order to achieve the objectives of the research in this article, here are some 
definitions, lemmas, and propositions related to graceful coloring. 
Definition 1. [4] Graceful 𝑘-coloring of graph G is proper vertex coloring 𝑐:𝑉(𝐺) →
{1,2,…,𝑘}, where 𝑘 ≥ 2 induces proper edge coloring 𝑐′:𝐸(𝐺) → {1,2,…,𝑘 − 1 defined 
𝑐′(𝑢𝑣) = |𝑐(𝑢) − 𝑐(𝑣)|. Proper vertex coloring c of graph G is graceful coloring if c is 
graceful k-coloring for 𝑘 ∈ 𝛮. 
Definition  2. [4] The graceful chromatic number of a graph 𝐺, denoted 𝜒𝑔(𝐺), is the 

minimum 𝑚 where 𝐺 has graceful 𝑚-coloring. 
Definition 3. [10] The amalgamation operation 𝑎𝑚𝑎𝑙(𝐺𝑖,𝑣0𝑖, 𝑡) is a graph operation used 
to obtain a new graph by gluing all graphs 𝐺𝑖 as much as t at the terminal point (𝑣0𝑖). 
Lemma 1. [4] If 𝐻 is a subgraph of a graph 𝐺, then 𝜒𝑔(𝐺) ≥ 𝜒𝑔(𝐻).  

Lemma 2. [4] it follows that if 𝐺 is a nontrivial connected graph, then 𝜒𝑔(𝐺) ≥ Δ(𝐺) + 1, 

where Δ(𝐺) is maximum degree in 𝐺. 
Proposition 1. [4] For each integer 𝑛 ≥ 5, 𝜒𝑔(𝑃𝑛) = 4 

 

METHODS  

The method used in this research is the axiomatic deductive method and pattern 
recognition. The detection method is used to find coloring patterns and graceful 
chromatic numbers on the result of the amalgamation operation of point family tree 
graphs. 

RESULTS AND DISCUSSION  

In this article, we determine the graceful chromatic numbers in graphs resulting 
from the amalgamation vertex of family tree graphs. The following are the results of the 
research presented in four theorems. 
Theorem 1. Based on Definition 3, given a graph of  𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) for 𝑛 ≥ 3, then the 
graceful coloring chromatic number is 

𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) = {
4,

𝑚 + 1,

for 𝑚 =  2

for 𝑚 ≥ 3 .
 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 434 

Proof. The graph 𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) has a vertex set 𝑉(𝑎𝑚𝑎𝑙(𝑝𝑛,𝑣,𝑚)) = {𝑥𝑗
𝑖│1 ≤ 𝑖 ≤ 𝑚,1 ≤

𝑗 ≤ 𝑛 − 1} ∪ {𝑣} and an edge set 𝐸(𝑎𝑚𝑎𝑙(𝑝𝑛,𝑣,𝑚)) = {𝑣𝑥1
𝑖 ,𝑥𝑗𝑥𝑗+1 |1 ≤ 𝑖 ≤ 𝑚,1 ≤ 𝑗 ≤

𝑛 − 2}. Proving graceful chromatic numbers on a graph 𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) will be divided into 
two cases as follows. 
Case 1. 𝑚 = 2 

We know that graph 𝑃𝑛 is a subgraph of graph 𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚), such that based on 
Lemma 1 and Proposition 1 we get 𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≥ 𝜒𝑔(𝑃𝑛) = 4 or  𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≥

4. Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≤ 4, define a proper vertex coloring 𝑐 ∶

𝑉(𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) → {1,2,…,4} as follows 

𝑓(𝑣) =

{
 
 

 
 
1,

2,

3,

4,

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

for  𝑣 ∈ {𝑥𝑖
1, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},{𝑥𝑖

2, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1}

for  𝑣 ∈ {𝑥𝑖
1, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},{𝑥𝑖

2, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1}

for  𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) →

{1,2,3}coloring as follows. 

 

𝑓(𝑒) =

{
 
 

 
 1,

2,

for  𝑒 ∈ {𝑉𝑥1
1},{𝑥𝑖

1𝑥𝑖+1
1 , 𝑖 ≡ 0 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2},

{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 1 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2}

for  𝑒 ∈ {𝑣𝑥1
2},{𝑥𝑖

1𝑥𝑖+1
1 , 𝑖 ≡ 1 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2},

{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 0 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2}

 

𝑓 is a graceful 4−coloring of 𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≤ 4, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) = 4. 

Case 2. 𝑚 ≥ 3 
We know that ∆(𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) = 𝑚, such that based on Lemma 2 we get 

𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≥ ∆ (𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) + 1 = 𝑚 + 1 or 𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≥ m + 1. 

Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≤ m + 1, define a proper vertex coloring 

𝑐 ∶ 𝑉(𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) → {1,2,…,m + 1} as follows. 

𝑓(𝑣) =

{
 
 
 
 

 
 
 
 
1,

2,

3,

4,

 𝑧 + 1

for  𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚}

,

for  𝑣 ∈ {𝑥𝑖
1, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},{𝑥𝑖

2, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚}

for  𝑣 ∈ {𝑥𝑖
1, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},{𝑥𝑖

2, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚}

for  𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚}

for  𝑣 ∈ {𝑥𝑖
𝑧,1 ≤ 𝑧 ≤ 𝑚}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) →
{1,2,…,m} coloring as follows. 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 435 

𝑓(𝑒) =

{
 
 
 
 

 
 
 
 

1,

2,

𝑧,

 𝑧 − 1,

for 𝑒 ∈ {𝑥𝑖
1𝑥𝑖+1

1 , 𝑖 ≡ 0 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2},

{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 1 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2;3 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑖
1𝑥𝑖+1

1 , 𝑖 ≡ 1 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2},

{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 0 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 2);1 ≤ 𝑖 ≤ 𝑛 − 2;3 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑉𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,3 ≤ 𝑧 ≤ 𝑚}

 

𝑓 is a graceful 𝑚 + 1−coloring of 𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) ≤ m + 1, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) = m + 1. 

Theorem 2. Based on Definition 3, given a graph of 𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) for 𝑛 ≥ 5, then the 
graceful coloring chromatic number is 

𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) = {
5,

𝑚 + 1,

for 𝑚 ≤  3

for 𝑚 ≥ 4.
 

Proof. The graph 𝑎𝑚𝑎𝑙(C𝑝𝑛,𝑣,𝑚) has a vertex set 𝑉(𝑎𝑚𝑎𝑙(C𝑝𝑛,𝑣,𝑚)) =
{𝑥𝑖

𝑧|1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑦𝑖
𝑧|1 ≤ 𝑖 ≤ 𝑛 − 1;  1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑣} and an edge set 

𝐸(𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚)) = {𝑣𝑥1
𝑧|1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑥𝑖

𝑧𝑥𝑖+1
𝑧 |1 ≤ 𝑧 ≤ 𝑚;1 ≤ 𝑖 ≤ 𝑛 − 1} ∪

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧|1 ≤ 𝑖 ≤ 𝑛 − 1;  1 ≤ 𝑧 ≤ 𝑚}. Proving graceful chromatic numbers on a graph 
𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) will be divided into two cases as follows. 
Case 1. 𝑚 ≤ 3 

We know that graph 𝑃𝑛 is a subgraph of graph 𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚), such that based on 
Lemma 1 and Proposition 1 we get 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≥ 𝜒𝑔(𝑃𝑛) = 4 or  

𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≥ 4. The proper vertex coloring will induce supposed 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) = 4, and it is known that the centipede is a subgraph of the 

𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚). Then graceful coloring can be done on the centipede graph first. The 
proper side coloring is as follows. Given a graph 𝐶𝑝𝑛, according to the definition of 

graceful coloring of edges 𝑐′(𝑥2𝑥3) ≠ 𝑐′(𝑥3𝑥4) ≠ 𝑐′(𝑥3𝑦2). Based on the several 
possibilities that have been obtained, we can see that the color of edge 3 that is formed 
can only be formed using a combination colors of vertex 1 and 4. While coloring the color 
of the next edge 3, we cannot do it.  So it can be concluded if 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≥ 5. 

Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≤ 5, define a proper vertex coloring 𝑐 ∶

𝑉(𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚)) → {1,2,…,5} as follows 

𝑓(𝑣) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

4,

5,

 𝑧 + 1,

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛}

,

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛},{𝑦1

2}

for 𝑣 ∈ {𝑦𝑖
1,1 ≤ 𝑖 ≤ 𝑛 − 1},{𝑦𝑖

2,1 < 𝑖 ≤ 𝑛 − 1},{𝑦𝑖
3,1 ≤ 𝑖 ≤ 𝑛 − 1}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛}

for 𝑣 ∈ {𝑥𝑖
𝑧,1 ≤ 𝑧 ≤ 3}

 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 436 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚)) →
{1,2,…,4} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
1,

2,

3,

4,

 𝑧,

for 𝑒 ∈ {𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},{𝑥1
2𝑥2

2},{𝑥1
3𝑥2

3},{𝑥2
1𝑦1

1}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3𝑥𝑖+1

3 , 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},{𝑥2
2𝑦1

2},{𝑥1
1𝑥2

1}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 3},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3𝑥𝑖+1

3 , 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1}

for 𝑒 ∈ {𝑉𝑥1
𝑧,1 ≤ 𝑧 ≤ 3}

 

There is graceful m+1−coloring of 𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≤ m + 1, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) = m + 1. 

Case 2. For 𝑚 ≥  4 
We know that ∆(𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚)) = m, such that based on Lemma 2 we get 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≥ ∆ (𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚)) + 1 = 𝑚 + 1 or 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≥ m + 1. 

Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≤ m + 1, define a proper vertex coloring 

𝑐 ∶ 𝑉(𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚)) → {1,2,…,m + 1} as follows. 

𝑓(𝑣) =

{
 
 
 
 
 
 
 

 
 
 
 
 
 
 

1,

2,

3,

4,

5,

 𝑧 + 1,

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛},{𝑥𝑖

𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;4 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}, ,

{𝑥𝑖
3, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛},{𝑦1

2}

for 𝑣 ∈ {𝑦𝑖
1,1 ≤ 𝑖 ≤ 𝑛 − 1},{𝑦𝑖

2,1 < 𝑖 ≤ 𝑛 − 1},

{𝑦𝑖
𝑧,1 ≤ 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛},

{𝑥𝑖
𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;4 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛},

{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛;4 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧,1 ≤ 𝑧 ≤ 𝑚}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚)) →
{1,2,…,m} coloring as follows. 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 437 

𝑓(𝑒) =

{
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 

1,

2,

3,

4,

 𝑧 − 1,

𝑧,

for 𝑒 ∈ {𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},{𝑥1
2𝑥2

2},{𝑥1
3𝑥2

3},{𝑥2
1𝑦1

1},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3𝑥𝑖+1

3 , 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1},

{𝑥𝑖+1
3 𝑦𝑖

3, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1},{𝑥2
2𝑦1

2},{𝑥1
1𝑥2

1}

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑖+1
𝑧 𝑦𝑖

𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 ≤ 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 3},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 3},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 3 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
3𝑥𝑖+1

3 , 𝑖 ≡ 1 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1}

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 4);1 < 𝑖 ≤ 𝑛 − 1;4 ≤ 𝑧 ≤ 𝑚},

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,4 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑉𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

  

There is graceful 𝑚 + 1−coloring of 𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) ≤ m + 1, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝐶𝑝𝑛,𝑣,𝑚) = m + 1. 

Theorem 3. Based on Definition 3, given a graph of 𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) for 𝑛 ≥ 4 and 𝑘 −

𝑛 ≥ 3, then the graceful coloring chromatic number is  

𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) = {
𝑘 − 𝑛 + 2,    

𝑚 + 1,

for  𝑚 + 𝑛 <  𝑘 + 1 

 for  𝑚 + 𝑛 ≥  𝑘 + 1.
 

Proof. The graph 𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) has a vertex set 𝑉(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) =

{𝑥𝑖
𝑧,𝑦𝑗

𝑧|1 ≤ 𝑖 ≤ 𝑛 − 1,1 ≤ 𝑗 ≤ 𝑘 − 𝑛,1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑣} and an edge set 

𝐸(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) = {𝑣𝑥1
𝑧,𝑥𝑖

𝑧𝑥𝑖+1
𝑧 ,𝑥𝑖+1

𝑧 𝑦𝑗
𝑧|1 ≤ 𝑖 ≤ 𝑛 − 2,1 ≤ 𝑗 ≤ 𝑘 − 𝑛,1 ≤ 𝑧 ≤ 𝑚}. 

Proving graceful chromatic numbers on a graph 𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) will be divided into two 

cases as follows. 
Case 1. For 𝑚 + 𝑛 <  𝑘 + 1 

We know that ∆(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) = 𝑘 − 𝑛 + 1, such that based on Lemma 2 we get 
𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≥ ∆ (𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) + 1 = 𝑘 − 𝑛 + 2 or 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≥ 𝑘 −

n + 2. Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≤ k − n + 2, define a proper vertex 

coloring 𝑐 ∶ 𝑉(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) → {1,2,…,k − n + 2} as follows. 
  



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 438 

Subcase 1. 𝑛 ≡ 1 (mod 3) 

𝑓(𝑣) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

4,

 𝑧 + 1,

 
𝑗 + 2,

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚}

untuk 𝑣 ∈ {𝑦2
𝑧,1 ≤ 𝑧 ≤ 2}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;3 ≤ 𝑧 ≤ 𝑚},

untuk 𝑣 ∈ {𝑥𝑖
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑦𝑗
𝑧,3 ≤ 𝑗 ≤ 𝑘 − 𝑛;1 ≤ 𝑧 ≤ 2},

{𝑦𝑗
𝑧,1 ≤ 𝑗 ≤ 𝑘 − 𝑛;3 ≤ 𝑧 ≤ 𝑚}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) →
{1,2,…,k − n + 1} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 
 
 

 
 
 
 
 
 

1,

2,

3,

𝑧,

 

𝑧 − 1,

𝑗 + 1,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;3 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑛−1
𝑧 𝑦1

𝑧,1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑛−1
2 𝑦2

𝑧,1 ≤ 𝑧 ≤ 2},{𝑥1
1𝑥2

1}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;3 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑉𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,2 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑛−1
𝑧 𝑦𝑗

𝑧,3 ≤ 𝑗 ≤ 𝑘 − 𝑛;1 ≤ 𝑧 ≤ 2}

{𝑥𝑛−1
𝑧 𝑦𝑗

𝑧,1 ≤ 𝑗 ≤ 𝑘 − 𝑛;3 ≤ 𝑧 ≤ 𝑚}

 

Subcase 2. For 𝑛 ≡ 2 (mod 3) 

𝑓(𝑣) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

4,

 𝑧 + 1,

𝑗 + 1,

 𝑘 − 𝑛 + 2,

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥2
3},{𝑥2

𝑧,5 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 2 and 𝑧 = 4},

{𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 𝑛 − 2;𝑧 = 3 dan 5 ≤ 𝑧 ≤ 𝑚},

for 𝑣 ∈ {𝑥𝑖
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑦𝑗
𝑧,1 ≤ 𝑗 ≤ 𝑘 − 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑛−1
𝑧 ,1 ≤ 𝑧 ≤ 𝑚}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) →
{1,2,…,k − n + 1} coloring as follows. 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 439 

𝑓(𝑒) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

𝑧,

𝑧 − 2

 
𝑘 − 𝑛 + 1,

𝑘 − 𝑛 − 𝑗 + 1,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 3;1 ≤ 𝑧 ≤ 𝑚},

{𝑥1
𝑧𝑥2

𝑧,2 ≤ 𝑧 ≤ 4}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 3;1 ≤ 𝑧 ≤ 𝑚},

{𝑥2
𝑧𝑥3

𝑧,5 ≤ 𝑧 ≤ 𝑚},{𝑥2
3𝑥3

3},{𝑥1
1𝑥2

1}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 𝑛 − 3;1 ≤ 𝑧 ≤ 𝑚},

{𝑥2
1𝑥3

1},{𝑥2
2𝑥3

2},{𝑥2
4𝑥3

4}

for 𝑒 ∈ {𝑉𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,5 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑛−2
𝑧 𝑥𝑛−1

𝑧 ,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑛−1
𝑧 𝑦𝑗

𝑧,1 ≤ 𝑗 ≤ 𝑘 − 𝑛;1 ≤ 𝑧 ≤ 𝑚}

 

Subcase 3. For 𝑛 ≡ 0 (mod 3) 

𝑓(𝑣) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

4,

 𝑧 + 1,

𝑗 + 1,

 𝑘 − 𝑛 + 2,

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 𝑚},

{𝑦1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥2
3},{𝑥2

𝑧,5 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 2;1 ≤ 𝑧 ≤ 2 dan 𝑧 = 4},

{𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 𝑛 − 2;𝑧 = 3 dan 5 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑦𝑗
𝑧,2 ≤ 𝑗 ≤ 𝑘 − 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑛−1
𝑧 ,1 ≤ 𝑧 ≤ 𝑚}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) →
{1,2,…,k − n + 1} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 
 
 

 
 
 
 
 
 

1,

2,

3,

𝑧,

𝑧 − 2
𝑘 − 𝑛

 
𝑘 − 𝑛 + 1,

𝑘 − 𝑛 − 𝑗 + 1,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 3;1 ≤ 𝑧 ≤ 𝑚},

{𝑥1
𝑧𝑥2

𝑧,2 ≤ 𝑧 ≤ 4}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 3;1 ≤ 𝑧 ≤ 𝑚},

{𝑥2
𝑧𝑥3

𝑧,5 ≤ 𝑧 ≤ 𝑚},{𝑥2
3𝑥3

3},{𝑥1
1𝑥2

1}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 𝑛 − 3;1 ≤ 𝑧 ≤ 𝑚},

{𝑥2
1𝑥3

1},{𝑥2
2𝑥3

2},{𝑥2
4𝑥3

4}

for 𝑒 ∈ {𝑉𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,5 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑛−2
𝑧 𝑥𝑛−1

𝑧 ,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑛−1
𝑧 𝑦1

𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑛−1
𝑧 𝑦𝑗

𝑧,2 ≤ 𝑗 ≤ 𝑘 − 𝑛;1 ≤ 𝑧 ≤ 𝑚}

 

There is graceful 𝑘 − 𝑛 − 2−coloring of 𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≤ 𝑘 − 𝑛 + 2, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) = 𝑘 − 𝑛 + 2. 

Case 2. For 𝑚 + 𝑛 ≥  𝑘 + 1 
We know that ∆(𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) = 𝑚, such that based on Lemma 2 we get 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≥ ∆ (𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚)) + 1 = m + 1 or 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≥ 𝑚 + 1. 

Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≤ m + 1 as same Case 1. 

  



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 440 

Theorem 4. Based on Definition 3, given a graph of 𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) for 𝑛 ≥ 2, then the 

graceful coloring chromatic number is 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) = {
4,       

𝑚 + 1,

for  𝑚 = 2

 for  𝑚 ≥ 3
 

Proof. The graph 𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) has a vertex set 𝑉(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) =

{𝑥𝑖
𝑧|1 ≤ 𝑖 ≤ 2𝑛 + 2,1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑦𝑖

𝑧│1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑣} and an edge set 

𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) = {𝑣𝑥1
𝑧|1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑥𝑖

𝑧𝑥𝑖+1
𝑧 |1 ≤ 𝑖 ≤ 2𝑛 +  1,1 ≤ 𝑧 ≤ 𝑚} ∪ 

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 |1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑧 ≤ 𝑚} ∪ {𝑥𝑛+1
𝑧 𝑦1

𝑧|1 ≤ 𝑧 ≤ 𝑚}. Proving graceful chromatic 

numbers on a graph 𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) will be divided into two cases as follows. 

Case 1. for 𝑚 = 2 
We know that graph 𝑃𝑛 is a subgraph of graph 𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚), such that based on 

Lemma 1 and Proposition 1 we get 𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≥ 𝜒𝑔(𝑃𝑛) = 4 or  

𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≥ 4. Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) ≤ k − n + 2, 

define a proper vertex coloring 𝑐 ∶ 𝑉(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) → {1,2,…,4} as follows. 
Subcase 1. For  𝑛 ≡ 1 (mod 3) 

𝑓(𝑣) =

{
 
 
 

 
 
 
1,

2,

3,

4,
 

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2},

{𝑦𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);3 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2},

{𝑥3
2},{𝑦𝑖

𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 < 𝑧 ≤ 2},{𝑥1
1} 

for 𝑣 ∈ {𝑥3
1},{𝑦1

𝑧,1 ≤ 𝑧 ≤ 2},{𝑥1
2}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2 },

{𝑦𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;  1 ≤ 𝑧 ≤ 2}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) →
{1,2,3} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 

 
 
 
 
1,

2,

3,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);3 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑛+1
𝑧 𝑦1

𝑧,1 ≤ 𝑧 ≤ 2},{𝑥2
1𝑥3

1},{𝑥1
2𝑥2

2},{𝑥3
2𝑥4

2},{𝑣𝑥1
1},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑦1
𝑧𝑦2

𝑧,1 ≤ 𝑧 ≤ 2},{𝑥2
2𝑥3

2},{𝑥1
1𝑥2

1},{𝑥3
1𝑥4

1},{𝑣𝑥1
2}

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

 

Subcase 2. For 𝑛 ≡ 2 (mod 3) 

𝑓(𝑣) =

{
 
 
 

 
 
 
1,

2,

3,

4,
 

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2},

{𝑦𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2},

{𝑥1
1},{𝑦𝑖

𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 < 𝑧 ≤ 2} 

for 𝑣 ∈ {𝑥1
2},{𝑦1

𝑧,1 ≤ 𝑧 ≤ 2}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2 },

{𝑦𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;  1 ≤ 𝑧 ≤ 2}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) →
{1,2,3} coloring as follows. 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 441 

𝑓(𝑒) =

{
 
 
 
 

 
 
 
 
1,

2,

3,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑦1
𝑧𝑦2

𝑧,1 ≤ 𝑧 ≤ 2},{𝑥1
2𝑥2

2},{𝑣𝑥1
1},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 0(𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑛+1
𝑧 𝑦1

𝑧,1 ≤ 𝑧 ≤ 2},{𝑥1
1𝑥2

1},{𝑣𝑥1
2}

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}

 

Subcase 3. 𝑛 ≡ 0 (mod 3) 

𝑓(𝑣) =

{
 
 
 

 
 
 
1,

2,

3,

4,
 

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2},

{𝑦𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}

for 𝑣 ∈ {𝑥𝑖
2, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2},

{𝑥1
1},{𝑦1

1},{𝑦𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 < 𝑧 ≤ 2} 

for 𝑣 ∈ {𝑥𝑖
1, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2},{𝑦1

2},{𝑥1
2}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2 },

{𝑦𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;  1 ≤ 𝑧 ≤ 2}

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) →
{1,2,3} coloring as follows. 

(𝑒) =

{
 
 
 
 

 
 
 
 
1,

2,

3,

for 𝑒 ∈ {𝑥𝑖
1𝑥𝑖+1

1 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1},

{𝑥1
2𝑥2

2},{𝑦1
2𝑦1

2},{𝑣𝑥1
1},{𝑥𝑖

2𝑥𝑖+1
2 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 0(𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 2}

for 𝑒 ∈ {𝑥𝑖
1𝑥𝑖+1

1 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1},

{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1},{𝑥𝑛+1
2 𝑦1

2},{𝑣𝑥1
2},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2},{𝑦2
1𝑦2

2}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 2}

 

 There is graceful 4−coloring of 𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≤ 4, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) = 4.  

Case 2. For 𝑚 ≥ 3 
We know that ∆(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) = m, such that based on Lemma 2 we get 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≥ ∆ (𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) + 1 = 𝑚 + 1 or 𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≥ m + 1. 

Furthermore, we prove that 𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≤ m + 1, define a proper vertex coloring 

𝑐 ∶ 𝑉(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) → {1,2,…,m + 1} as follows. 
Subcase 1. For 𝑛 ≡ 1 (mod 3) 

𝑓(𝑣) =

{
 
 
 
 

 
 
 
 

1,

2,

3,

4,

𝑧 + 1,
 

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);3 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 𝑚},

{𝑥3
2},{𝑦𝑖

𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 < 𝑧 ≤ 𝑚},{𝑥2
𝑧;3 ≤ 𝑧 ≤ 𝑚} 

for 𝑣 ∈ {𝑥3
1},{𝑥3

𝑧;3 ≤ 𝑧 ≤ 𝑚},{𝑦1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 𝑚 },

{𝑦𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;  1 ≤ 𝑧 ≤ 𝑚},{𝑥2

1},𝑥2
2}

for 𝑣 ∈ {𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚 }

 



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 442 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) →
{1,2,3,…,m} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

𝑧,

𝑧 − 1,

untuk 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);3 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑛+1
𝑧 𝑦1

𝑧,1 ≤ 𝑧 ≤ 𝑚},{𝑥2
1𝑥3

1},{𝑥3
2𝑥4

2},{𝑥2
𝑧𝑥3

𝑧,3 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑚}

untuk 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);2 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 𝑚},

{𝑦1
𝑧𝑦2

𝑧,1 ≤ 𝑧 ≤ 𝑚},{𝑥2
2𝑥3

2},{𝑥3
𝑧𝑥4

𝑧,𝑧 = 1 dan 3 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑀},{𝑥1
1𝑥2

1}

untuk 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑚}

untuk 𝑒 ∈ {𝑣𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

untuk 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,2 ≤ 𝑧 ≤ 𝑚}

 

Subcase 2. For 𝑛 ≡ 2 (mod 3) 

𝑓(𝑣) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

4,

𝑧 + 1,
 

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2}

{𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;3 ≤ 𝑧 ≤ 𝑚}

,

{𝑦𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 < 𝑧 ≤ 𝑚} 

for 𝑣 ∈ {𝑦1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 2 },

{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;3 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;  1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚 }

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶ 𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) →
{1,2,3,…,m} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 
 
 

 
 
 
 
 
 

1,

2,

3,

𝑧,

𝑧 − 1,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2}

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;3 ≤ 𝑧 ≤ 𝑚}
,

{𝑦1
𝑧𝑦2

𝑧,1 ≤ 𝑧 ≤ 𝑚},
{𝑦𝑖

𝑧𝑦𝑖+1
𝑧 , 𝑖 ≡ 0(𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑛+1
𝑧 𝑦1

𝑧,1 ≤ 𝑧 ≤ 𝑚},{𝑥1
1𝑥2

1},
{𝑦𝑖

𝑧𝑦𝑖+1
𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 2},

{𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;3 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑣𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,2 ≤ 𝑧 ≤ 𝑚}

 

  



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 443 

Subcase 3. For 𝑛 ≡ 0 (mod 3) 

𝑓(𝑣) =

{
 
 
 
 
 

 
 
 
 
 

1,

2,

3,

4,

𝑧 + 1,
 

for 𝑣 ∈ {𝑉},{𝑥𝑖
𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 𝑚}

for 𝑣 ∈ {𝑥𝑖
2, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2},

{𝑥2
𝑧,3 ≤ 𝑧 ≤ 𝑚},{𝑦𝑖

𝑧, 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 < 𝑧 ≤ 𝑚},

{𝑦1
𝑧,𝑧 = 1 dan 3 ≤ 𝑧 ≤ 𝑚}

 

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;𝑧 = 1 and 3 ≤ 𝑧 ≤ 𝑚}

{𝑦1
2},{𝑥1

2}
,

for 𝑣 ∈ {𝑥𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 2;1 ≤ 𝑧 ≤ 𝑚 },

{𝑦𝑖
𝑧, 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;  1 ≤ 𝑧 ≤ 𝑚},{𝑥2

1},{𝑥2
2}

for 𝑣 ∈ {𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚 }

 

The proper vertex coloring will induce the proper edge of 𝑐′ ∶
𝐸(𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚)) → {1,2,3,…,m} coloring as follows. 

𝑓(𝑒) =

{
 
 
 
 
 
 

 
 
 
 
 
 

1,

2,

3,

𝑧,

𝑧 − 1,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1,𝑧 = 1,

and 3 ≤ 𝑧 ≤ 𝑚,{𝑦1
2𝑦1

2},{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 0(𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛;1 ≤ 𝑧 ≤ 𝑚},

{𝑥𝑛+1
𝑧 𝑦1

𝑧,𝑧 = 1 dan 3 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 0 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;𝑧 = 1

and 3 ≤ 𝑧 ≤ 𝑚},{𝑥𝑖
2𝑥𝑖+1

2 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑚},

{𝑦2
𝑧𝑦2

𝑧,𝑧 = 1 and 3 ≤ 𝑧 ≤ 𝑚},{𝑥1
1𝑥2

1},{𝑥𝑛+1
2 𝑦1

2}
,

for 𝑒 ∈ {𝑥𝑖
𝑧𝑥𝑖+1

𝑧 , 𝑖 ≡ 1 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 2𝑛 + 1;1 ≤ 𝑧 ≤ 𝑚},

{𝑦𝑖
𝑧𝑦𝑖+1

𝑧 , 𝑖 ≡ 2 (𝑚𝑜𝑑 3);1 < 𝑖 ≤ 𝑛 − 1;1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑣𝑥1
𝑧,1 ≤ 𝑧 ≤ 𝑚}

for 𝑒 ∈ {𝑥1
𝑧𝑥2

𝑧,2 ≤ 𝑧 ≤ 𝑚}

 

There is graceful 𝑚 + 1−coloring of 𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚). Therefore, it obtained that 
𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) ≤ m + 1, hence 𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) = 𝑚 + 1. 

CONCLUSIONS 

Based on the discussion described in chapter four, four new theorems of graceful coloring 
are obtained from the amalgamation operation of vertex family tree graphs. The graceful 
chromatic number obtained is as follows. 

𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) = {
4,

𝑚 + 1,

for 𝑚 =  2

for 𝑚 ≥ 3 .
 

𝜒𝑔𝑎𝑚𝑎𝑙(𝑃𝑛,𝑣,𝑚) = {
5,

𝑚 + 1,

for 𝑚 ≤  3

for 𝑚 ≥ 4.
 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐵𝑘,𝑛,𝑣,𝑚) = {
𝑘 − 𝑛 + 2,    

𝑚 + 1,

for  𝑚 + 𝑛 <  𝑘 + 1 

 for  𝑚 + 𝑛 ≥  𝑘 + 1.
 

𝜒𝑔𝑎𝑚𝑎𝑙(𝐸3,𝑛,𝑣,𝑚) = {
4,       

𝑚 + 1,

for  𝑚 = 2

 for  𝑚 ≥ 3
 

  



on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family 

Arika Indah Kristiana 444 

REFERENCES 

[1] O. Levin, Discrete Mathematics. Greeley: University of Northern Colorado, 2019. 
[2] Hasmawati, Teori Graf. University Hassanudin, 2015. 
[3] G. Chartrand and P. Zhang, A First Course in Graph Theory. Boston: McGraw-Hill 

Higher Education, 2012. 
[4] P. Zhang, A Kaleidoscopic View of Graph Colorings. USA: Spinger, 2016. 
[5] S. English, P. Zhang, and Kalamazoo, “On graceful colorings of trees,” Math. Bohem., 

vol. 142, no. 1, pp. 57–73, 2017, doi: 10.21136/MB.2017.0035-15. 
[6] R. Mincu, C. Obreja, and A. Popa, “The Graceful Chromatic Number for Some 

Particular Classes of Graphs,” Proc. - 21st Int. Symp. Symb. Numer. Algorithms Sci. 
Comput. SYNASC 2019, no. September 2019, pp. 109–115, 2019, doi: 
10.1109/SYNASC49474.2019.00024. 

[7] R. Alfarisi, Dafik, R. M. Prihandini, R. Adawiyah, E. R. Albirri, and I. H. Agustin, 
“Graceful Chromatic Number of Unicyclic Graphs,” J. Phys. Conf. Ser., vol. 1306, no. 
1, 2019, doi: 10.1088/1742-6596/1306/1/012039. 

[8] N. A. Sania, Dafik, and A. Fatahillah, “Bilangan Kromatik Graceful pada Keluarga Graf 
Unicyclic Pendahuluan Lemma yang Digunakan Hasil Penelitian,” CGANT J. Math. 
Appl., vol. 1, no. 2, pp. 27–38, 2020, doi: 10.25037/cgantjma.v1i2.39. 

[9] S. Khoirunnisa, Dafik, A. I. Kristiana, R. Alfarisi, and E. R. Albirri, “On graceful 
chromatic number of comb product of ladder graph,” J. Phys. Conf. Ser., vol. 1836, 
no. 1, 2021, doi: 10.1088/1742-6596/1836/1/012027. 

[10] A. Arbain, “Bilangan Terhubung-Total Pelangi untuk Beberapa Graf Amalgamasi,” 
Saintifik, vol. 4, no. 1, pp. 18–23, 2018, doi: 10.31605/saintifik.v4i1.148. 

[11] L. D. Minarti, Dafik, S. Setiawani, Slamin, and A. Fatahillah, “Pewarnaan Sisi Dinamis 
pada Graf Hasil Operasi Amalgamasi Titik Keluarga Graf Pohon dan Kaitannya 
Dengan Keterampilan Berpikir Tingkat Tinggi,” Pap. Knowl. . Towar. a Media Hist. 
Doc., pp. 15–22, 2019. 

[12] A. F. Akadji, D. Taha, N. Lakisa, and N. I. Yahya, “Bilangan Terhubung Titik Pelangi 
Pada Amalgamasi Graf Berlian,” Euler  J. Ilm. Mat. Sains dan Teknol., vol. 7, no. 2, pp. 
56–61, 2019, doi: 10.34312/euler.v7i2.10345. 

[13] C. Sisi and G. Tangga, “Antimagic Total Selimut, Comb Sisi Graf Tangga Segitiga 
dengan Amalgamasi Graf Sikel,” Kadikma, 2017. 

[14] S. M. Citra, A. I. Kristiana, R. Adawiyah, Dafik, and R. M. Prihandini, “On the packing 
chromatic number of vertex amalgamation of some related tree graph,” J. Phys., vol. 
1836, no. 1, 2021, doi: 10.1088/1742-6596/1836/1/012025. 

[15] K. H. Rosen, Discrete Mathematics and Its Applications, 7th ed. New York: 
MCGraw,Hill, 2012. 

[16] A. K. Purnapraja, D. Dafik, and I. Azizah, “Super ( a , d ) - H -Antimagic Total Selimut 
pada Graf Shackle Kipas F4,” Pros. Semin. Nas. Mat. dan Pendidik. Mat. Vol 1, No 1, 
vol. 46, pp. 2–8, 2014. 

[17] S. Sriram, D. Ranganayakulu, I. Venkat, and K. G. Subramanian, “On Eccentric Graphs 
of Broom Graphs,” Ann. Pure Appl. Math., vol. 5, no. 2, pp. 146–152, 2014. 

[18] M. Ajmal, W. Nazeer, W. Khalid, and S. M. Kang, “Zagreb Polynomials and Multiple 
Zagreb Indices for the Line Graphs of Banana Tree Graph , Firecracker Graph,” Glob. 
J. Pure Appl. Math., vol. 13, no. 6, pp. 2659–2672, 2017.