On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles ()
1. Introduction
We consider undirected, simple, finite and connected graphs. For a graph
, we denote by
and
the sets of its vertices and edges, respectively. The set of edges of
incident with a vertex
is denoted by
. For any
,
denotes the degree of the vertex
in
. For a graph
,
denotes the maximum degree of a vertex of
. A simple cycle with
edges
is denoted by
. A simple path with
edges
is denoted by
. The terms and concepts that we do not define can be found in [1].
For an arbitrary finite set
, we denote by
the number of elements of
. The set of positive integers is denoted by
. For any subset
of the set
, we denote by
and
the subsets of all even and all odd elements of
, respectively.
An arbitrary nonempty subset of consecutive integers is called an interval. An interval with the minimum element
and the maximum element
is denoted by
. An interval
is called a
-interval if
.
For any real number
, we denote by
the maximum (minimum) integer which is less (greater) than or equal to
.
For any positive integer
define
.
For any nonnegative integer
define
![](https://www.scirp.org/html/9-1200131\e68e781c-6d1d-482a-aa01-a47d4a0a11c9.jpg)
A function
is called a proper edge
-coloring of a graph G, if all colors are used, and no two adjacent edges receive the same color.
The minimum value of
for which there exists a proper edge
-coloring of a graph
is denoted by
[2].
If
is a graph, and
is its proper edge
-coloring, where
, then we define
.
If
,
, and
is a proper edge
-coloring of a graph
, then we set
.
A proper edge
-coloring
![](https://www.scirp.org/html/9-1200131\fc213f75-81b8-4d33-a4fb-48b7b0c9c429.jpg)
of a graph
is called an interval
-coloring of
[35] if for any
, the set
is a
-interval. For any
, we denote by
the set of graphs for which there exists an interval
-coloring. Let
.
For any
, we denote by
and
the minimum and the maximum possible value of
, respectively, for which
. For a graph
, let us set
.
A proper edge
-coloring
![](https://www.scirp.org/html/9-1200131\1cda0843-1abb-4fb0-b15b-2a3e65ebed70.jpg)
of a graph
is called a cyclically interval
-coloring of
, if for any
, at least one of the following two conditions holds:
1)
is a
-interval2)
is a
-interval.
For any
, we denote by
the set of graphs for which there exists a cyclically interval
-coloring. Let
.
For any
, we denote by
and
the minimum and the maximum possible value of
, respectively, for which
. For a graph
, let us set
.
It is clear that for any
, an arbitrary interval
- coloring
of a graph
is also a cyclically interval
-coloring of
. Thus, for any
,
and
. Let us also note that for an arbitrary graph
,
. It is also clear that for any
, the following inequality is true:
![](https://www.scirp.org/html/9-1200131\08cea485-e46a-4fde-b190-f19fa82b897e.jpg)
and
![](https://www.scirp.org/html/9-1200131\f3c7a949-bc99-4d5f-a0c6-a6711b7eee21.jpg)
In [5,6], for any tree
, it is proved that
,
is an interval, and the exact values of the parameters
,
are found. In [7,8], for any tree
, it is proved that
. Some interesting results on cyclically interval
-colorings and related topics were obtained in [9-14].
In this paper, for any integer
, it is proved that
, and the set
is found.
2. Main Results
Remark 1. Clearly, for any integer
,
,
.
Therefore, if
, then a proper edge
coloring of
does not exist, and
.
Remark 2. It is not difficult to see that for any integer
,
and
.
Proposition 1. For any integer
,
,
![](https://www.scirp.org/html/9-1200131\1981619d-fba2-4713-8171-2dadf7d8cc82.jpg)
![](https://www.scirp.org/html/9-1200131\78cc3fcb-6e24-430b-a7dc-a877d994dffa.jpg)
![](https://www.scirp.org/html/9-1200131\e9e2b498-06b0-4793-8136-0fa82f0e6881.jpg)
Proof is trivial.
Theorem 1. For any integers
and
, satisfying the conditions
and
,
if and only if
.
Proof. First let us prove, that if
,
and
![](https://www.scirp.org/html/9-1200131\bc99ce29-1377-4901-878c-a0617367f16b.jpg)
then
.
Assume the contrary: there are
,
and
![](https://www.scirp.org/html/9-1200131\ad7e1d23-8f94-4f22-99ce-c3d45d4a55e8.jpg)
for which a cyclically interval
-coloring
of the graph
exists.
Let us construct a graph
removing from the graph
the subset
of its edges. Let us construct a graph
removing from the graph
all its isolated vertices.
Case A.
is a connected graph.
Let us denote by
the simple path with pendant edges
and
which is isomorphic to the graph
.
Case A.1.
is odd.
Clearly,
. It means that
is an even number, satisfying the inequality
.
Case A.1.1.
is odd.
Clearly,
. Since
is a cyclically interval
-coloring of
, we conclude from the definition of
, that for a graph
, there exists an interval
-coloring
with
. Consequently, the number
is odd, what contradicts the same parity of
and
.
Case A.1.2.
is even.
Clearly,
. Since
is a cyclically interval
-coloring of
, we conclude from the definition of
, that for a graph
, there exists an interval
-coloring
with
and
. Consequently, the number
is even, what contradicts the different parity of
and
.
Case A.2.
is even.
Clearly,
. It means that
is an odd number, satisfying the inequality
.
Case A.2.1.
is odd.
Clearly,
. Since
is a cyclically interval
-coloring of
, we can conclude from the definition of
, that for a graph
, there exists an interval
-coloring
with
. Consequently,
![](https://www.scirp.org/html/9-1200131\4329a60e-73d0-49a2-9ebb-4365f45c0256.jpg)
which is impossible.
Case A.2.2.
is even.
Clearly,
. Since
is a cyclically interval
-coloring of
, we can conclude from the definition of
, that for a graph
, there exists an interval
-coloring
with
and
.
Since
is odd, the number
is also odd, but it is impossible because of the same parity of
and
.
Case B.
is a graph with
connected components,
.
Assume that:
1)
are connected components of
numbered in succession at bypassing of the graph
in some fixed direction2)
are vertices of
numbered in succession at bypassing mentioned in 1)3)
are edges of
numbered in succession at bypassing mentioned in 1)4)
,
,
,
.
Define functions
,
,
![](https://www.scirp.org/html/9-1200131\2c56a21a-7c10-41a7-8073-ea62360196d8.jpg)
as follows. For any
, set:
![](https://www.scirp.org/html/9-1200131\51385d20-efcb-46ba-b048-ec7b3e9c8df0.jpg)
.
For any
, set
![](https://www.scirp.org/html/9-1200131\32fd7e26-ae48-4661-919d-3b4b861109b3.jpg)
Now let us define subgraphs
of the graph
.
For any
, let
be the subgraph of
induced by the subset
![](https://www.scirp.org/html/9-1200131\09e596ef-e3ba-45b7-bc13-31edc7c04e31.jpg)
of its vertices. Let
be the subgraph of
induced by the subset
![](https://www.scirp.org/html/9-1200131\d2c0287c-b6f5-4fb2-b390-fd304e0e5476.jpg)
of its vertices.
Let
![](https://www.scirp.org/html/9-1200131\d9335cf9-0d40-46a6-bf30-f0a0173c0d4c.jpg)
.
For any
, we define a point
of the 2- dimensional rectangle coordinate system by the following way:
.
Let us define a graph
. Set
![](https://www.scirp.org/html/9-1200131\c8031a84-7de4-4dff-82cc-dfe7373efa4c.jpg)
![](https://www.scirp.org/html/9-1200131\b78e7cf1-5fd8-4978-879d-43cdf9d61574.jpg)
Clearly,
.
Let
,
.
An edge
of the graph
is called horizontal if the points
and
have the same ordinate.
Let us denote by
the set of all horizontal edges of the graph
. Set
. It is easy to note that the numbers
and
are both even.
Now let us define a function ![](https://www.scirp.org/html/9-1200131\a0013df7-c54c-4646-9e9f-87293b65666b.jpg)
by the following way. For an arbitrary
set:
![](https://www.scirp.org/html/9-1200131\6d56f338-d042-4498-a62a-3953ba6f15f1.jpg)
Clearly,
.
Case B.1.
is odd.
Clearly,
. It means that
is an even number, satisfying the inequality
. It is not difficult to see that in this case, for an arbitrary
,
is odd, and, moreover, for an arbitrary
,
is even. Since
is even, we conclude that the odd number
![](https://www.scirp.org/html/9-1200131\14a7ede3-6929-4487-b9a9-c0e38ee542c3.jpg)
is represented as a sum of two even numbers, which is impossible.
Case B.2.
is even.
Clearly,
.
It means that
is an odd number, satisfying the inequality
.
It is not difficult to see that in this case, for an arbitrary
,
is odd, and, moreover, for an arbitrary
,
is even.
Case B.2.1.
.
In this case, evidently, there are different integers
and
in the set
, for which there exist interval
-colorings
and
of the graphs
and
, respectively. Consequently,
![](https://www.scirp.org/html/9-1200131\5e089bf2-6fb9-4e03-9616-9ab10f5efcc4.jpg)
which is impossible.
Case B.2.2.
.
Without loss of generality assume that
.
Since
is even, we conclude that the even number
![](https://www.scirp.org/html/9-1200131\f1ba0c80-1dc2-4709-b6d6-fad63b7005e4.jpg)
is represented as a sum of one odd and two even numbers, which is impossible.
Case B.2.3.
.
Clearly, for any
, the set
contains exactly one of the colors 1 and
.
Case B.2.3.a).
,
.
It is not difficult to see that in this case there is
, for which the set
contains the color
. It means that there exists an interval
-coloring of the graph
which colors pendant edges of
by the color 1. Consequently,
which is impossible.
Case B.2.3.b).
,
.
It is not difficult to see that in this case there is
, for which the set
contains the color 2. It means that there exists an interval
- coloring of the graph
which colors pendant edges of
by the color 1. Consequently,
which is impossible.
Case B.2.3.c).
,
.
Let us choose
and
satisfying the conditions
,
.
Let
be the maximum color of the set
.
Let
be the minimum color of the set
.
Clearly,
.
It is not difficult to see that there exists an interval
-coloring of the graph
which colors pendant edges of
by the color 1. Hence,
.
It is not difficult to see that there exists an interval
-coloring of the graph
which colors pendant edges of
by the color 1. Hence,
.
Consequently, we obtain that
![](https://www.scirp.org/html/9-1200131\af8a8f12-bac4-4255-a327-5703a645353b.jpg)
which is impossible.
Thus, we have proved that if
,
and
then
.
Now let us prove that if
,
,
,
then
.
Assume the contrary. It means that there are
,
, and
, which satisfy the conditions
and
![](https://www.scirp.org/html/9-1200131\d3ada552-46aa-4a08-b895-caac4c7e3ef2.jpg)
Case 1.
is odd.
In this case
and
, andtherefore,
. It means that there exists
, for which
.
Let us note that the equality
implies
, which is incompatible with the condition
. Hence,
.
Now, to see a contradiction, it is enough to note that the existence of an interval
-coloring of a graph
with the existence of an interval 2-coloring of a graph
provides the existence of a cyclically interval
-coloring of the graph
.
Case 2.
is even.
In this case
and
and, therefore,
.
It follows from Remark 2 that
.
Clearly, there exists
,
for which
.
Let us note that the equality
![](https://www.scirp.org/html/9-1200131\e92022a2-5678-45a9-8169-46b4a78961c2.jpg)
implies
, which is incompatible with the condition
. Hence,
![](https://www.scirp.org/html/9-1200131\20e9892c-bf5f-483b-bf77-0f5f172d2294.jpg)
is an even number, satisfying the inequality
.
Now, to see a contradiction, it is enough to note that the existence of an interval
-coloring of a graph
![](https://www.scirp.org/html/9-1200131\f2d4a055-1a4d-4d3c-a55f-ac8b04748037.jpg)
with the existence of an interval 2-coloring of a graph
![](https://www.scirp.org/html/9-1200131\38027e4f-75ff-487e-bfe3-6b13b6f3b9a3.jpg)
provides the existence of a cyclically interval
-coloring of the graph
.
Thus, we have proved, that if
,
,
,
then
.
Theorem 1 is proved.
It means that we also have Theorem 2. For an arbitrary integer
,
![](https://www.scirp.org/html/9-1200131\81e2d0f9-fc91-4e75-ab69-362ebdf39496.jpg)
3. Acknowledgements
The author thanks P.A. Petrosyan and N.A. Khachatryan for their attention to this work.