1. Introduction
For terms and symbols related to graph theory that are not covered in this paper, please see the book [1]. In 1968, Alexander Rosa received his Ph.D from Slovak Academy of Science under Anton Kotzig after he published his paper titled “On certain valuations of the vertices of a graph,” which is the source of many labelings. The most attention of his labeling is β -valuation, which recalled a graceful labeling by Solomon W. Golomb [2]. Graph coloring is one of the most useful models in graph theory. Many problems relating to computer registers allocation, electronic bandwidth allocation, and school scheduling have all been resolved using it.
Let G be a graph with vertex set
and edge set
. A labeling
such that
for every two adjacent edges e and
in G is called proper edge coloring.
We frequently have an interest in proper edge coloring that use a minimum number of colors which called chromatic index (edge chromatic number)
of a graph G. A graph G is k-colorable, if
, and G is k-chromatic, if
.
Maheo and Sacle in [3] studied the irregular-sum chromatic index for connected graph G with vertex set
and edge set
of order
. A proper edge coloring
for some integer
is called an irregular-sum chromatic coloring of G if the induced vertex coloring
defined by
is irregular (vertex-distinguishing). The minimum positive integer for which G has such an irregular-sum chromatic coloring is called an irregular-sum chromatic index of G and is denoted by
.
In [4] [5], Ping Zhang introduced the labeling for a graph G of order
. Let
,
be an unrestricted edge coloring (where the adjacent edges may be colored the same). The edge coloring c induces a vertex coloring
defined by
where the sum is computed in
. For some positive integer
, such an edge coloring c is always present. The modular edge-gracefulness
of G is the minimum
for which such a vertex-distinguishing edge coloring of G exists. Thus,
for every connected graph G of order
. If
, then G is called a modular edge-graceful graph and a vertex-distinguishing edge coloring
is called a modular edge-graceful labeling as well as a modular edge-graceful coloring of G.
Based on established graph coloring ideas and inspired by irregular-sum and modular edge-graceful labeling we present a new concept for coloring graphs focusing on proper coloring in this paper.
Let
be the set of all positive integers and let
denoted the set of edges incident with
in G. For a connected simple graph
of order
, A proper edge coloring
induces a proper vertex coloring
, defined by
The minimum positive integer for which G has NK-labeling is called NK-chromatic index and denoted by
. A graph G with chromatic number
is called a k-NKcolorable graph. If no such k, the graph G is not NK-colorable.
2. Preliminaries
Proposition 2.1 For any connected graph G
where
is the maximum degree of G.
Proposition 2.2 If G is a connected graph of order at least 3 such that G contains two adjacent vertices of maximum degree, then
.
An illustration of the NK-chromatic index. We show in Figure 1,
and from preposition 2.2,
. Hence,
.
Figure 1. An illustration of NK-labeling.
3. Well Known Classes of Graphs
We now turn our attention to two other well-known classes of graphs, namely path and cycles.
Theorem 3.1 Let n be an integer greater than 4, the NK-chromatic index of the path
of order n is three.
Proof. By preposition 2.2,
. To prove
, for
, assign the edge
by a color c as following.
Case 1:
, the previous edge color induces the following proper vertex coloring for
given by
Hence,
.
Case 2:
. For
, we show the NK-labeling of
in Figure 2, so
.
Figure 2. NK-labeling of P4.
For
, the previous edge color induces the following proper vertex coloring for
given by
Hence,
.
Case 3:
. For
, we show the NK-labeling of
in Figure 3, so
.
Figure 3. NK-labeling of P5.
For
, the previous edge color induces the following proper vertex coloring for
given by
Hence,
. Therefore, for
the NK-chromatic index of
is 3.
Theorem 3.2 Let n be an integer greater than 3, the NK-chromatic index of the cycle
of order n is
Proof. Case 1:
.
Trivially we can show that
. Now consider the cycle
. Clearly,
by using the Proposition 2.2. We want to prove that
. For
, the edge
assigned by a color c as following
So, we get a proper vertex coloring as following, for
,
Therefore,
.
Case 2:
Clearly for any three consecutive edges in
, they cannot color by i, j, i, otherwise we get improper vertex coloring. Hence we start to color
by 1,
by 2,
by 3,
by 1,
by 2 and so on. Since
, we end with
. Then we need a new color 4 for the edge
, otherwise we get improper vertex coloring. Therefore
.
To prove that
, for
we show in Figure 4,
.
Figure 4. NK-labeling of C4.
For
, for
, we did as case 1 with
Then we get a proper vertex coloring as following, for
,
Hence,
.
Case 3:
.
We start to color
by 1,
by 2,
by 3,
by 1,
by 2 and so on. Since
, we end with
. For the edges
and
we have to use new colors 4, 5 respectively, otherwise we get improper vertex coloring. Hence
. To show
. For
, we show in Figure 5,
.
Figure 5. NK-labeling of C5.
For
, for
,
Then we get a proper vertex coloring as following, for
,
Now we will focus on some well-known classes of graph with odd order.
Theorem 3.3 Let S be a star of odd order
, the NK-chromatic index of S is
.
Proof. Let
where
,
,
. Color the edge
by
, which induces a proper vertex coloring
Hence,
. Moreover, by preposition 2.1, we have
because
.
Theorem 3.4 For odd integer
. Let
be a wheel of order
, the NK-chromatic index of
is
Proof. Let
where
,
,
. By proposition 2.1,
. It is reminded to prove that
.
Case 1:
. Assign the colors of the edge e as following
We get three types of 3-cycle
1-
,
,
2-
,
3-
,
First, suppose that there exist two vertices of
have same color. Thus
or
. Assume that
Which impossible since
. So, we may assume that
Since 3 is prime, 3 divides
which implies that
is a multiple of n, contradiction. Hence
,
has proper vertex-coloring. Moreover, according on the edge coloring
,
,
. Thus,
and
have a proper vertex-coloring. This implies
.
Next, if
, then assign the colors of the edge e as following
We get four types of 3-cycle
1-
,
,
2-
,
3-
,
4-
,
As above we can prove that
has proper vertex coloring. First, suppose that there exist two vertices of
have same color. Thus
or
. Assume that
Which impossible since
. So, we may assume that
Since
, there is integer k such that
so
which implies that 5 is a multiple of 3, contradiction. Hence
has proper vertex-coloring. Moreover, according to the edge coloring
,
,
and
.Thus
,
and
have proper vertex coloring. Hence,
.
Theorem 3.5 For odd integer
, the NK-chromatic index of the complete graph
is n.
Proof. The graph
is
-regular graph with size
. Moreover, for odd order n,
. From Proposition 2.1,
. We will color the edges of
by proper edge coloring using this n colors. Therefore, every vertex in
incident with
different colors. We will denote the vertex that incident with the colors
by
. Each color
belong to all
such that
, otherwise
. Since
and from the definition of NK-labeling,
. It is clear that for
,
.
An example of odd complete graph, Figure 6 illustrate
so NK-chromatic index of
is 7.
Figure 6. The NK-labeling of K7.
Proposition 3.6 If G is a graph of size
, then
where
is the maximum number of edges in an independent set of edges of a graph G.
Proof. Suppose that
and that
are the edge color classes in k-edge coloring of G. Thus
for each
(
). Moreover, from the definition of NK-labeling, it is clear that
. Therefore if
,
are the color classes of
such that
, then
for all
. Hence
.
Some of the complete graphs
,
are NK-colorable,
. From Figure 7,
. Now, suppose that
can be color by using 4 colors. We may assume that
in Figure 2. Since c is a proper edge coloring, none of the edges
,
,
and
can be colored by the color 1. Hence two of these four edges must be assigned the same color and the remaining two edges must be assigned different colors, otherwise
which is impossible. Assume
,
and
. The last edge should be colored by the color 1, but in this case
, contradiction. Therefore
. Hence,
.
Figure 7. The NK-labeling of K4.
Problem: For even integer
, determine the NK-chromatic index of the complete graph
if it exists.
4. Conclusion
Graph labeling is one of the main topics of graph theory, and it is used in a variety of fields, such as coding theory, X-ray crystallography, radar, astronomy, circuit design, communication network addressing, and database management. In this article, we introduced a new concept of graph labeling and found the NK-labeling of special graphs such as path, cycle, wheel, star, and complete graph for some n. Furthermore, we find the lower bound of our labeling.