SIGNED GRAPHS FROM PROPER

COLORING OF GRAPHS

Divya Antoney*

Department of Mathematics CHRIST (Deemed to be University) Bengaluru, India.

divya.antoney@res.christuniversity.in

Tabitha Agnes Mangam

Department of Mathematics CHRIST (Deemed to be University) Bengaluru, India.

tabitha.rajashekar@christuniversity.in

Mukti Acharya

Department of Mathematics CHRIST (Deemed to be University) Bengaluru, India.

mukti1948@gmail.com

Reception: 29/03/2023 Acceptance: 22/05/2023 Publication: 12/06/2023

Suggested citation:

Antoney, D., Mangam, T. A. and Acharya, M. (2023). Signed graphs from

proper coloring of graphs. 3C Tecnología. Glosas de innovación aplicada a

la pyme, 12(2), 148-161. https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

148

SIGNED GRAPHS FROM PROPER

COLORING OF GRAPHS

Divya Antoney*

Department of Mathematics CHRIST (Deemed to be University) Bengaluru, India.

divya.antoney@res.christuniversity.in

Tabitha Agnes Mangam

Department of Mathematics CHRIST (Deemed to be University) Bengaluru, India.

tabitha.rajashekar@christuniversity.in

Mukti Acharya

Department of Mathematics CHRIST (Deemed to be University) Bengaluru, India.

mukti1948@gmail.com

Reception: 29/03/2023 Acceptance: 22/05/2023 Publication: 12/06/2023

Suggested citation:

Antoney, D., Mangam, T. A. and Acharya, M. (2023). Signed graphs from

proper coloring of graphs. 3C Tecnología. Glosas de innovación aplicada a

la pyme, 12(2), 148-161. https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

ABSTRACT

Let denote the chromatic number of a graph . Under the proper coloring of a

graph G with

colors, we define a signed graph from it. The obtained signed

graph is defined as parity colored signed graph and denoted as

. The signs of

edges of are defined from the colors of the vertices as if the colors on the

adjacent vertices are of the same (opposite) parity. In this paper, we initiate a study on

. We further investigate the chromatic rna number of some classes of graphs

concerning proper coloring.

KEYWORDS

Signed graph, parity colored signed graph of a graph, chromatic rna number.

INDEX

χ(G)

+( −)

ABSTRACT

KEYWORDS

1. INTRODUCTION

1.1. Preliminaries

2. RESULTS ON Sc

3. CHARACTERIZATION OF Sc

4. CHROMATIC rna NUMBER

5. CONCLUSION

6. ACKNOWLEDGMENT

REFERENCES

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

149

1. INTRODUCTION

In this paper, we consider simple connected graphs. The smallest positive integer

such that such that whenever ab is an edge in

is called the chromatic number of and it is denoted by .

In [7], the concept of a signed graph has been introduced. Let

be a

signed graph with the signature of , where

is the

underlying graph of . The edges of receiving sign are called the positive

(negative) edges of . A signed graph is all positive (negative) if all the edges of are

positive (negative). A homogeneous signed graph is a signed graph in which either all

the edges are positive or all negative and heterogeneous, otherwise.

denotes the negative (positive) edge set of the signed graph and

is the edge set. In [2], by the negation, we mean a signed

graph obtained by reversing the sign of every edge . By we

mean the number of negative (positive) edges incident to

and

. The positive (negative) edges in

are represented by solid

(dashed) line segments as shown in Figure 1. The negative section of a signed is

the maximal connected edge-induced subgraph in

consisting of only the negative

edges as defined in [2].

Motivated by the definition of rna number

[3], we initiate the concept of

chromatic rna of . For a detailed study of the rna number, we refer to [4,9–11]. The

signed graphs and are isomorphic if there exists a one-to-

one correspondence between the vertex sets which preserves adjacency and signs

on it.

A triangular Snake graph is obtained from a path on vertices in which

every edge is replaced by a triangle. The sign of a cycle (path) in a signed graph is

the product of the signs of its edges. A cycle is said to be positive if the product of the

signs of the edges is positive or the cycle has an even number of negative edges. A

signed graph is said to be balanced if all the cycles in are positive [7]. Therefore,

acyclic signed graphs are always balanced. Two vertices and of

are of the

same parity if their colors and are both odd or both even and of opposite

parity otherwise [4].

Motivated by the concept of set coloring in signed graphs [1] and induced signed

graphs [5], we initiate a study on of a graph. We refer to [6,8,12,13] for our study.

Throughout the paper, by we mean parity colored signed graph of a graph.

1.1. PRELIMINARIES

Definition 1.1. Let be a set of colors and be

an onto function. Then parity colored signed graph of a graph (

, in short) is

defined by taking the signature function for every edge in as:

f:V(G)→{1,2,…, k}

f(a)≠f(b)

χ(G)

S= (G,σ)

σ:E(G)→{+,−}

+( −)

E−(S)(E+(S))

E(S)=E−(S)∪E+(S)

η(S)

d−(v)(d+(v))

d(v) = d−(v)+d+(v)

σ−(G)

S= (G,σ)

S′ =(H,σ′

)

TS(L)

L+ 1

c(u)

c(v)

A= {1,2,…, χ(G)}

c:V(G)→A

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

150

1. INTRODUCTION

In this paper, we consider simple connected graphs. The smallest positive integer

such that such that whenever ab is an edge in

is called the chromatic number of and it is denoted by .

In [7], the concept of a signed graph has been introduced. Let be a

signed graph with the signature of , where is the

underlying graph of . The edges of receiving sign are called the positive

(negative) edges of . A signed graph is all positive (negative) if all the edges of are

positive (negative). A homogeneous signed graph is a signed graph in which either all

the edges are positive or all negative and heterogeneous, otherwise.

denotes the negative (positive) edge set of the signed graph and

is the edge set. In [2], by the negation, we mean a signed

graph obtained by reversing the sign of every edge . By we

mean the number of negative (positive) edges incident to and

. The positive (negative) edges in are represented by solid

(dashed) line segments as shown in Figure 1. The negative section of a signed is

the maximal connected edge-induced subgraph in consisting of only the negative

edges as defined in [2].

Motivated by the definition of rna number [3], we initiate the concept of

chromatic rna of . For a detailed study of the rna number, we refer to [4,9–11]. The

signed graphs and are isomorphic if there exists a one-to-

one correspondence between the vertex sets which preserves adjacency and signs

on it.

A triangular Snake graph is obtained from a path on vertices in which

every edge is replaced by a triangle. The sign of a cycle (path) in a signed graph is

the product of the signs of its edges. A cycle is said to be positive if the product of the

signs of the edges is positive or the cycle has an even number of negative edges. A

signed graph is said to be balanced if all the cycles in are positive [7]. Therefore,

acyclic signed graphs are always balanced. Two vertices and of are of the

same parity if their colors and are both odd or both even and of opposite

parity otherwise [4].

Motivated by the concept of set coloring in signed graphs [1] and induced signed

graphs [5], we initiate a study on of a graph. We refer to [6,8,12,13] for our study.

Throughout the paper, by we mean parity colored signed graph of a graph.

1.1. PRELIMINARIES

Definition 1.1. Let be a set of colors and be

an onto function. Then parity colored signed graph of a graph ( , in short) is

defined by taking the signature function for every edge in as:

f:V(G)→{1,2,…, k}

f(a)≠f(b)

χ(G)

S= (G,σ)

σ:E(G)→{+,−}

+( −)

E−(S)(E+(S))

E(S)=E−(S)∪E+(S)

η(S)

d−(v)(d+(v))

d(v) = d−(v)+d+(v)

σ−(G)

S= (G,σ)

S′ =(H,σ′

)

TS(L)

L+ 1

c(u)

c(v)

A= {1,2,…, χ(G)}

c:V(G)→A

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

Example 1. In Figure 1(a) we show a proper coloring of a graph and in Figure 1(b)

its .

Figure 1. A graph with its Sc

Definition 1.2. The chromatic rna number of a graph , denoted by , is the

smallest number of negative edges in with respect to any proper coloring of .

2. RESULTS ON Sc

Now we investigate some properties of .

Observation 2.1. is positive homogeneous if

From the definition of , we can see that it is not unique. Does there exist a graph

whose Sc is unique? The answer is yes as shown below.

Proposition 2.2. on a complete graph is unique up to isomorphism.

Proof. The chromatic number of is n with as the

vertex coloring. Since is uniquely colored under , there is exactly one on up

to isomorphism.

Theorem 2.3. Every non-trivial of order will have at least one negative edge.

Proof. Let G be a non-trivial graph with and .

Therefore, . If , then there exist at least two vertices colored

with and . Therefore, will have a negative edge between these two vertices. So

let . Under the proper coloring of the graph, there exists a vertex

colored with which is adjacent to vertices colored with .

If the vertex is colored with an odd (even) number, then the edge between and the

vertex colored with is a negative edge in . Hence the result follows.

c(uv) =

{+ , c(u)

and

c(v)

are both odd or both even

−,

Otherwise.

σ−

c(G)

∀vi∈V(Sc),c(vi)≡1(mod2)

(c(vi)≡0(mod2))

c:V(Kn)→{1,2,…, n}

χ(G)=k≤n

|V(G)|≥2

χ(G)=k≥2

χ(G)=2

χ(G)=k> 2

{1,2,…m−1,m+ 1,…k}

2(1)

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

151

The following theorem gives the balanced nature of .

Theorem 2.4. of graph is balanced.

Proof. Consider of and let

represent the colors with odd (even) positive

numbers. If is acyclic, then obviously is balanced. Assume that

contains at

least one cycle. Consider an arbitrary cycle in . Without loss of generality, let

be the cycle on the vertices . Consider a path on the vertices

of the cycle . Then, there are two cases:

Case 1: Under the function , if the end vertices of

are colored with numbers of

the same parity, then of

will have an even number of negative edges, and the

edge between and

will receive a positive sign. We can observe that when

vertices of opposite colors are adjacent in a cycle, it will always induce two negative

edges as seen in Figure 2. Therefore the cycle has an even number of negative

edges.

Figure 2. on

Case 2: Under the function , if the end vertices of

are colored with numbers of

opposite parity, then of

will have an odd number of negative edges and the edge

between and will receive a negative sign as seen in Figure 3.

Figure 3. on

In both cases, any cycle in has an even number of negative edges. Therefore,

is always balanced.

The converse need not be true as we know that positive homogeneous signed

graphs are always balanced. However,

can never be a positive homogeneous

signed graph. This observation leads to the next result.

oi(ei)

v1v2…vkv1

v1v2…vk

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

152

The following theorem gives the balanced nature of .

Theorem 2.4. of graph is balanced.

Proof. Consider of and let represent the colors with odd (even) positive

numbers. If is acyclic, then obviously is balanced. Assume that contains at

least one cycle. Consider an arbitrary cycle in . Without loss of generality, let

be the cycle on the vertices . Consider a path on the vertices

of the cycle . Then, there are two cases:

Case 1: Under the function , if the end vertices of are colored with numbers of

the same parity, then of will have an even number of negative edges, and the

edge between and will receive a positive sign. We can observe that when

vertices of opposite colors are adjacent in a cycle, it will always induce two negative

edges as seen in Figure 2. Therefore the cycle has an even number of negative

edges.

Figure 2. on

Case 2: Under the function , if the end vertices of are colored with numbers of

opposite parity, then of will have an odd number of negative edges and the edge

between and will receive a negative sign as seen in Figure 3.

Figure 3. on

In both cases, any cycle in has an even number of negative edges. Therefore,

is always balanced.

The converse need not be true as we know that positive homogeneous signed

graphs are always balanced. However, can never be a positive homogeneous

signed graph. This observation leads to the next result.

oi(ei)

v1v2…vkv1

v1v2…vk

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

Theorem 2.5. The negation of

is balanced if and only if the underlying graph of

is bipartite.

Proof. Let and

be the parity-colored signed graph and its negation

respectively. Assume that is balanced. Therefore, every cycle in

contains an even number of negative edges. This implies Sc contains an even number

of positive edges. From Theorem 2.4, every cycle in

contains an even number of

negative edges. Now, every cycle of

has an even number of negative and positive

edges. Therefore, the underlying graph of is bipartite.

Assume is a bipartite graph. Therefore, every cycle in

is of even length. From

Theorem 2.4, every cycle in

contains an even number of negative edges. Hence

is balanced.

Remark 1. A subsigned graph of need not be .

Figure 4

The underlying graph of the signed graph in Figure 4(a) has chromatic number 3.

Therefore, the

in Figure 4(a) has at least one positive edge. Furthermore, the

underlying graph of the signed graph in Figure 4(b) has chromatic number 2.

Therefore, the

of Figure 4(b) is negative homogeneous. In Figure 4(a), the edges

and will receive a positive sign. However, the subsigned graph with the same

vertices will receive negative signs only since its chromatic number is 2. Therefore,

the subsigned graph of need not be .

Remark 2. The parity-colored signed graphs of graph need not be isomorphic.

The parity-colored signed graphs of Figure 5(a) are shown in Figure 5(b) and

Figure 5(c). We can observe that they are not isomorphic to each other.

η(Sc)

v3v4

v4v6

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

153

Figure 5

3. CHARACTERIZATION OF Sc

In this section, we will characterize

of some classes of graphs like bipartite

graphs, cycles, and wheels. We also explore the ’chromatic rna’ number of some

classes of graphs concerning proper coloring.

We have already noted that there exists at least one negative edge in .

Therefore, it is impossible to have a positive homogeneous . So we aim at finding a

negative homogeneous .

Theorem 3.1.

is negatively homogeneous if and only if its underlying graph is

bipartite.

Proof. Assume that is negatively homogeneous. From the balanced nature of ,

its vertices can be partitioned into two subsets such that the edges between them are

negative. Therefore, the vertices can be colored with two colors. This implies that the

underlying graph of is bipartite.

The converse is easy to see as is bipartite and we need only two colors to color

its vertices and get a negative homogeneous signed graph. Hence the result.

Corollary 3.2. of is negative homogeneous if and only if is and

being or bipartite graph.

Corollary 3.3. of is negative homogenous if and only if is and

being .

We have seen that

is balanced. Next, we discuss the nature of a negative

section in of a cycle.

Proposition 3.4. The negative section in of a cycle is always of even length

or a whole cycle of even length.

Proof. We know that , when k is even (odd). Therefore, there exists

at least one vertex colored with in . In the proper coloring of

, the vertex

colored with is adjacent to the vertex colored with or

. This will give negative

edges between the vertices colored with and or and . Therefore, the negative

G1∘G2

G1+G2

χ(Ck)= 2(3)

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

154

Figure 5

3. CHARACTERIZATION OF Sc

In this section, we will characterize of some classes of graphs like bipartite

graphs, cycles, and wheels. We also explore the ’chromatic rna’ number of some

classes of graphs concerning proper coloring.

We have already noted that there exists at least one negative edge in .

Therefore, it is impossible to have a positive homogeneous . So we aim at finding a

negative homogeneous .

Theorem 3.1. is negatively homogeneous if and only if its underlying graph is

bipartite.

Proof. Assume that is negatively homogeneous. From the balanced nature of ,

its vertices can be partitioned into two subsets such that the edges between them are

negative. Therefore, the vertices can be colored with two colors. This implies that the

underlying graph of is bipartite.

The converse is easy to see as is bipartite and we need only two colors to color

its vertices and get a negative homogeneous signed graph. Hence the result.

Corollary 3.2. of is negative homogeneous if and only if is and

being or bipartite graph.

Corollary 3.3. of is negative homogenous if and only if is and

being .

We have seen that is balanced. Next, we discuss the nature of a negative

section in of a cycle.

Proposition 3.4. The negative section in of a cycle is always of even length

or a whole cycle of even length.

Proof. We know that , when k is even (odd). Therefore, there exists

at least one vertex colored with in . In the proper coloring of , the vertex

colored with is adjacent to the vertex colored with or . This will give negative

edges between the vertices colored with and or and . Therefore, the negative

G1∘G2

G1+G2

χ(Ck)= 2(3)

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

section of is of even length and when k is even the cycle will have all negative

edges.

The next theorem gives the characterization of the signed cycle which is the Sc of

its underlying graph.

Theorem 3.5. A signed cycle on k vertices is if and only if satisfies any

one of the following:

(i) is negatively homogeneous for even .

(ii) is heterogeneous for odd with length of each negative section even.

Proof. In , the number of negative sections is equal to the number of positive

sections. Let , be the negative (positive) sections in a signed

cycle.

Case 1: For even , is a bipartite graph. From Theorem 3.1, of is negative

homogeneous. Hence (i) follows.

Case 2: For odd , is heterogeneous. From Proposition 3.4, the length of each

negative section is even. Hence (ii) follows.

Figure 6. of and

Sufficiency is easy to see in Figure 6.

The next theorem gives the characterization of

on a wheel having an odd

number of vertices.

Theorem 3.6. A signed wheel for an odd integer is if and

only if satisfies any one of the following:

(

lpi

)

,1 ≤i≤

⌊k

2⌋

Wn=Cn−1+K1

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

155

(i) is positive homogeneous and .

(ii) is negative homogeneous, and

the distance between the vertices which are the end vertices of the positive

edge lying on the Cn−1 is two.

Proof. We know that ( is odd). The vertices of can be colored in

two ways such that the edges of are either positive (negative) homogeneous. If

the vertices on the cycle are colored with 1 and 3 (1 and 2 or 2 and 3), then is

positive (negative) homogeneous respectively.

Case 1: If is positive homogeneous, the vertex of will be colored with 2

only and the edges joining K1 to all the vertices of are negative.

Therefore, . Thus (i) holds.

Case 2: If is negative homogeneous, then the vertex of can be colored

with 1 or 3. Then the edges joining to all the vertices of are negative (positive)

depending upon the colors on the and it is easy to see that the distance between

any two vertices lying on which have a positive edge incident on them is two. We

can observe that and .

Therefore, . Thus (ii) holds.

Figure 7. of

Sufficiency part is easy to see in Figure 7.

E−

(

)

=E+

(

)

Cn−1

E−

(

)

|−|E+

(

)

=n−

χ(Wn)= 3

Cn−1

−(

)

Cn−1

E−

(

)

=n−1 +

n−1

E+

(

)

n−1

E−

(

)

|−|E+

(

)

=n−

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

156

(i) is positive homogeneous and .

(ii) is negative homogeneous, and

the distance between the vertices which are the end vertices of the positive

edge lying on the Cn−1 is two.

Proof. We know that ( is odd). The vertices of can be colored in

two ways such that the edges of are either positive (negative) homogeneous. If

the vertices on the cycle are colored with 1 and 3 (1 and 2 or 2 and 3), then is

positive (negative) homogeneous respectively.

Case 1: If is positive homogeneous, the vertex of will be colored with 2

only and the edges joining K1 to all the vertices of are negative.

Therefore, . Thus (i) holds.

Case 2: If is negative homogeneous, then the vertex of can be colored

with 1 or 3. Then the edges joining to all the vertices of are negative (positive)

depending upon the colors on the and it is easy to see that the distance between

any two vertices lying on which have a positive edge incident on them is two. We

can observe that and .

Therefore, . Thus (ii) holds.

Figure 7. of

Sufficiency part is easy to see in Figure 7.

E−(Wn)=E+(Wn)

Cn−1

E−(Wn)|−|E+(Wn)=n−1

χ(Wn)= 3

Cn−1

E−(Wn)=E+(Wn)

Cn−1

E−(Wn)=n−1 + n−1

E+(Wn)=n−1

E−(Wn)|−|E+(Wn)=n−1

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

Theorem 3.7. A signed graph on is if and only if the following conditions

hold:

(i) Every cycle in has exactly two negative edges and

(ii) For a vertex whose , its

is either 4 or 2, and

is due to two negative edges incident at lying in two adjacent

triangles.

Proof. Assume that is . We know that . From the definition

of , each triangle of will have 2 negative edges. Hence (i) follows.

Now we prove (ii), let vertex whose has . That

is, there is an edge in a triangle whose end vertices receive same color. This is a

contradiction. Similarly we can show that and . Therefore,

can be or . In other words, or . If and two negative edges

lie in the same triangle then the adjacent triangle will have exactly one negative edge,

which is not possible. Thus

is due to the negative edges lying in two

adjacent triangles. When , the proof is easy to see. Thus (ii) follows.

Figure 8. of

Further sufficiency is easy to see. of

is shown in Figure 8. Hence the

proof.

4. CHROMATIC RNA NUMBER

Definition 4.1. The chromatic rna number of a graph , denoted by , is the

smallest number of negative edges in with respect to any proper coloring of .

We investigate the ‘chromatic rna’ number of bipartite graphs, complete graphs,

multipartite graphs, and cycle-related graphs.

Proposition 4.2. For any bipartite graph .

Proof. From Theorem 3.1,

of a bipartite graph is negative homogeneous.

Therefore, .

Proposition 4.3. For any complete graph ,

TS(L)

v∈V(TS(L))

d(v) = 4

d−(v)

d(v)=2

TS(L)

χ(TS(L)) = 3

TS(L)

v∈V(TS(L))

d(v) = 4

d+(v) = 4

d+(v)≠3

d+(v)≠1

d+(v)

d−(v)=2

d−(v) = 4

TS(3)

σ−

c(G)

B,σ−

c(B)=|E(B)|

σ−

c(B)=|E(B)|

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

157

Proof. From Proposition 2.2, the of a complete graph, is unique up to

isomorphism. We know that . Let be the set of vertices colored with

even (odd) positive integers from the set . The edges of that occur

across the set receive a negative sign. That is, the total number of negative

edges is .

Case 1: When is even, . Hence, .

Therefore, .

Case 2: When is odd, . Hence, .

Therefore, . Hence de proof

Proposition 4.4. For any complete r-partite graph ,

Proof. From Proposition 2.2, the Sc of a complete r-partite graph, is unique

up to isomorphism and its chromatic number is . Let be the set of vertices

colored with even (odd) positive integers from the set . The edges of

will receive a negative sign if and only if they occur between the sets and

. Since each set has n elements, the total number of negative edges is .

Case 1: When is even, . Hence, .

Therefore, .

Case 2: When is odd, . Hence, .

Therefore, . Hence the proof.

We observe that the chromatic rna number of bipartite graphs, complete graphs,

and complete multipartite graphs with respect to proper coloring is equal to the

number of negative edges in them respectively. Next, we discuss a class of graphs for

which it does not hold true.

Proposition 4.5. For any cycle ,

−

c(Kn)=

4,n is even.

n2−1

is odd

χ(Kn)=n

X(Y)

{1,2,…, n}

X(Y)

|X∥Y|

X|=|Y|=

X∥Y|=

−

c(Kn)=

X|=

n−1

,|Y|=

n+ 1

X||Y|=

n2−1

−

c(Kn)=

n2−1

Kn,n,…,n

−

c(Kn,n,…n)=

4n2,r is even

r2−1

n2,r

is odd

Kn,n,…,n

X(Y)

{1,2,…, r}

Kn,n,…,n

|X∥Y|n2

X|=|Y|=

X∥Y|=

−

c(Kn,n,…n)=

X|=

r−1

,|Y|=

r+ 1

X∥Y|=

r2−1

−

c(Kn,n,…nn)

r2−1

−

c(Ck)=

{k,k is even.

2, k is odd.

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

158

Proof. From Proposition 2.2, the of a complete graph, is unique up to

isomorphism. We know that . Let be the set of vertices colored with

even (odd) positive integers from the set . The edges of that occur

across the set receive a negative sign. That is, the total number of negative

edges is .

Case 1: When is even, . Hence, .

Therefore, .

Case 2: When is odd, . Hence, .

Therefore, . Hence de proof

Proposition 4.4. For any complete r-partite graph ,

Proof. From Proposition 2.2, the Sc of a complete r-partite graph, is unique

up to isomorphism and its chromatic number is . Let be the set of vertices

colored with even (odd) positive integers from the set . The edges of

will receive a negative sign if and only if they occur between the sets and

. Since each set has n elements, the total number of negative edges is .

Case 1: When is even, . Hence, .

Therefore, .

Case 2: When is odd, . Hence, .

Therefore, . Hence the proof.

We observe that the chromatic rna number of bipartite graphs, complete graphs,

and complete multipartite graphs with respect to proper coloring is equal to the

number of negative edges in them respectively. Next, we discuss a class of graphs for

which it does not hold true.

Proposition 4.5. For any cycle ,

σ−

c(Kn)=

4,n is even.

n2−1

4,n is odd

χ(Kn)=n

X(Y)

{1,2,…, n}

X(Y)

|X∥Y|

|X|=|Y|=n

|X∥Y|=n2

σ−

c(Kn)=n2

|X|=n−1

2,|Y|=n+ 1

|X||Y|=n2−1

σ−

c(Kn)=n2−1

Kn,n,…,n

σ−

c(Kn,n,…n)=

4n2,r is even

r2−1

4n2,r is odd

Kn,n,…,n

X(Y)

{1,2,…, r}

Kn,n,…,n

|X∥Y|n2

|X|=|Y|=r

|X∥Y|=r2

σ−

c(Kn,n,…n)=r2

4n2

|X|=r−1

2,|Y|=r+ 1

|X∥Y|=r2−1

σ−

c(Kn,n,…nn)r2−1

4n2

σ−

c(Ck)={k,k is even.

2, k is odd.

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

Proof. For any cycle , we have the following two cases:

Case 1: The cycle on the even number of vertices is a bipartite graph. From

Theorem 3.5, the of the cycle is negatively homogeneous.

Therefore, ( is even).

Case 2: Let the vertices of the cycle be vi such that and

. From Theorem 2.3 and Theorem 2.4, is balanced,

and will have at least one negative edge. Therefore, at least two negative edges

exist in . Let the edges be v1vk, and . Since the chromatic number of the

odd cycle is three, let be the vertex coloring function.

Consider the following coloring.

The vertices are colored with . The vertices are

colored with , and the vertex is colored with . This coloring gives two negative

edges in the . Therefore, ( is odd).

Proposition 4.6. Le is a graph having k cycles with exactly one vertex in

common and the length of each cycle is greater than or equal to . If m cycles are of

odd length and the remaining cycles are of even length then,

Proof. Consider a graph having k cycles with exactly one vertex in common. We

arrange the cycles in such a way that the first m cycles are of odd length and the

remaining cycles are of even length.

Case 1: If contains cycles only on an even number of vertices, then is a

bipartite graph. From Theorem 3.5, .

Case 2: If contains cycles only on the odd number of vertices, then .

From Theorem 3.5, cycles on the odd number of vertices will have a minimum of two

negative edges. From Proposition 4.5, .

Case 3: If contains cycles on odd and even numbers of vertices, then clearly

. In this case cycles on even number vertices can be colored with 1 and 3

such that they have zero negative edges. From Proposition 4.5, cycles on the odd

number of vertices will have a minimum of two negative edges. Therefore,

. Hence the proof.

Proposition 4.7. For a triangular snake graph .

The following result gives the characterization of a graph with respect to a specific

rna number associated with it.

σ−

c(Ck)=k

vivi+1 ∈E(Ck)

vkv1∈E(Ck)∀i,1 ≤i<k

vk−1vk

C:V(Ck)→{1,2,3}

v1,v3, …vk−2

v2,v4, …vk−1

σ−

c(Ck)= 2

−

c(G) =

|E(G)|,

If all cycles are even.

2k, If all cycles are odd.

otherwise

σ−

c(G)=|E(G)|

χ(G)=3

σ−

c(G)=2k

χ(G)=3

σ−

c(G)=2m

TS(L), σ−

c(TS(L)) = 2L

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

159

Proposition 4.8. if and only if is .

We know that there exists more than one graph whose rna number is , for

. Is it possible to construct with a given rna number? The answer is yes.

Theorem 4.9. There exists for every natural number n such that σc−(G) = n.

Proof. For every n ∈ N, consider a path on vertices. From Theorem 3.1,

the path is always negative homogeneous. Therefore, there exists with a given rna

number.

We also have some other graphs such as with fixed rna numbers.

5. CONCLUSION

In the paper, we have initiated a study on . We have given the characterization of

on some classes of graphs. We have investigated the rna number with respect to

the proper coloring of some classes of graphs and we have also shown the existence

of graphs with a given rna number.

6. ACKNOWLEDGMENT

We thank the referees and express gratitude for their valuable suggestions.

REFERENCES

(1)

Acharya, B. D. (2012). Set-valuations of a signed digraph. Journal of

Combinatorics, Information & System Sciences, 37, 145-167.

(2) Acharya, M. (2017). C- Cordial coloring in Signed Graphs. Electronics Notes of

Discrete Mathematics, 63, 11-22.

(3) Acharya, M., & Kureethara, J. V. (2021). Parity coloring in Signed Graphs. J.

Prime Research in Math., 17(2), 1-7.

(4) Acharya, M., Kureethara, J. V., & Zaslavasky, T. (2021). Characterizations of

some parity signed graphs. Australasian Journal of Combinatorics, 81(1),

89-100.

(5) Aniyan, A., & Sudev, N. K. (2020). Induced Signed Graphs of some classes of

Graphs. Proceedings of the Jangjeon Mathematical Society, 2, 283–291.

(6) Chartrand, G., & Zang, P. (2011). Chromatic Graph Theory. Chapman and Hall/

CRC Press.

(7) Harary, F. (1953). On the notion of balance of a signed graph. Michigan Math. J.,

2(6), 143-146.

(8) Jensen, T. R., & Toft, B. (2011). Graph Coloring Problems. John Wiley and Sons.

(9) Kureethara, J. V. (2020). New developments in the study of parity signed graphs.

AIP Conference Proceedings, 2261(1), 020001.

σ−

c(G)=1

n∈ ℕ

n≥2

Pn+1

n+ 1

K1,n

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

160

Proposition 4.8. if and only if is .

We know that there exists more than one graph whose rna number is , for

. Is it possible to construct with a given rna number? The answer is yes.

Theorem 4.9. There exists for every natural number n such that σc−(G) = n.

Proof. For every n ∈ N, consider a path on vertices. From Theorem 3.1,

the path is always negative homogeneous. Therefore, there exists with a given rna

number.

We also have some other graphs such as with fixed rna numbers.

5. CONCLUSION

In the paper, we have initiated a study on . We have given the characterization of

on some classes of graphs. We have investigated the rna number with respect to

the proper coloring of some classes of graphs and we have also shown the existence

of graphs with a given rna number.

6. ACKNOWLEDGMENT

We thank the referees and express gratitude for their valuable suggestions.

REFERENCES

(1) Acharya, B. D. (2012). Set-valuations of a signed digraph. Journal of

Combinatorics, Information & System Sciences, 37, 145-167.

(2) Acharya, M. (2017). C- Cordial coloring in Signed Graphs. Electronics Notes of

Discrete Mathematics, 63, 11-22.

(3) Acharya, M., & Kureethara, J. V. (2021). Parity coloring in Signed Graphs. J.

Prime Research in Math., 17(2), 1-7.

(4) Acharya, M., Kureethara, J. V., & Zaslavasky, T. (2021). Characterizations of

some parity signed graphs. Australasian Journal of Combinatorics, 81(1),

89-100.

(5) Aniyan, A., & Sudev, N. K. (2020). Induced Signed Graphs of some classes of

Graphs. Proceedings of the Jangjeon Mathematical Society, 2, 283–291.

(6) Chartrand, G., & Zang, P. (2011). Chromatic Graph Theory. Chapman and Hall/

CRC Press.

(7) Harary, F. (1953). On the notion of balance of a signed graph. Michigan Math. J.,

2(6), 143-146.

(8) Jensen, T. R., & Toft, B. (2011). Graph Coloring Problems. John Wiley and Sons.

(9) Kureethara, J. V. (2020). New developments in the study of parity signed graphs.

AIP Conference Proceedings, 2261(1), 020001.

σ−

c(G)=1

n∈ ℕ

n≥2

Pn+1

n+ 1

K1,n

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

(10)

Reshma, R., Gayathri, H., & Rajendran, S. (2021). On some parameters of parity

signed graphs. Turkish Journal of Computer and Mathematics Education, 12(13),

1992-1998.

(11)

Sehrawat, D., & Bhattacharjya, B. (accepted). rna number of some parity signed

generalized Peterson graphs. Communications in Combinatorics and

Optimization.

(12) West, D. B. (1999). Introduction to Graph Theory. Prentice Hall of India.

(13) Zaslavsky, T. (1982). Signed Graphs. Discrete Applied Mathematics, 4(1), 47-74.

https://doi.org/10.17993/3ctecno.2023.v12n2e44.148-161

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed.44 | Iss.12 | N.2 April - June 2023

161