Open Journal of Discrete Mathematics
Vol.3 No.1(2013), Article ID:27386,6 pages DOI:10.4236/ojdm.2013.31009
On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles
Institute for Informatics and Automation Problems, The National Academy of Sciences of Republic of Armenia, Yerevan, Republic of Armenia
Email: rrkamalian@yahoo.com
Received November 23, 2012; revised December 23, 2012; accepted December 31, 2012
Keywords: Proper Edge Coloring; Cyclically Interval Coloring; Simple Cycle
ABSTRACT
A proper edge t-coloring of a graph G is a coloring of its edges with colors 1,2,···,t such that all colors are used, and no two adjacent edges receive the same color. A cyclically interval t-coloring of a graph G is a proper edge t-coloring of G such that for each its vertex x, either the set of colors used on edges incident to x or the set of colors not used on edges incident to x forms an interval of integers. For an arbitrary simple cycle, all possible values of t are found, for which the graph has a cyclically interval t-coloring.
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
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
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
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:
and
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,
,
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
then.
Assume the contrary: there are,
and
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,
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
,
,
as follows. For any, set:
.
For any, set
Now let us define subgraphs of the graph
.
For any, let
be the subgraph of
induced by the subset
of its vertices. Let be the subgraph of
induced by the subset
of its vertices.
Let
.
For any, we define a point
of the 2- dimensional rectangle coordinate system by the following way:
.
Let us define a graph. Set
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
by the following way. For an arbitrary set:
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
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,
which is impossible.
Case B.2.2..
Without loss of generality assume that
.
Since is even, we conclude that the even number
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
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
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
implies, which is incompatible with the condition
. Hence,
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
with the existence of an interval 2-coloring of a graph
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,
3. Acknowledgements
The author thanks P.A. Petrosyan and N.A. Khachatryan for their attention to this work.
REFERENCES
- D. B. West, “Introduction to Graph Theory,” PrenticeHall, Upper Saddle River, 1996.
- V. G. Vizing, “The Chromatic Index of a Multigraph,” Kibernetika, Vol. 3, 1965, pp. 29-39.
- A. S. Asratian and R. R. Kamalian, “Interval Colorings of Edges of a Multigraph,” Applied Mathematics, Vol. 5, Yerevan State University, 1987, pp. 25-34. (in Russian)
- A. S. Asratian and R. R. Kamalian, “Investigation of Interval Edge-Colorings of Graphs,” Journal of Combinatorial Theory, Series B, Vol. 62, No. 1, 1994, pp. 34-43. doi:10.1006/jctb.1994.1053
- R. R. Kamalian, “Interval Edge Colorings of Graphs,” Doctoral Dissertation, The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990. (in Russian)
- R. R. Kamalian, “Interval Colorings of Complete Bipartite Graphs and Trees,” Preprint of the Computing Centre of the Academy of Sciences of Armenia, 1989. (in Russian)
- R. R. Kamalian, “On a Number of Colors in Cyclically Interval Edge Colorings of Trees,” Research Report LiTHMAT-R-2010/09-SE, Linkoping University, 2010.
- R. R. Kamalian, “On Cyclically-Interval Edge Colorings of Trees,” Buletinul Academiei de Stiinte a Republicii Moldova Matematica, Vol. 68, No. 1, 2012, pp. 50-58.
- A. Kotzig, “1-Factorizations of Cartesian Products of Regular Graphs,” Journal of Graph Theory, Vol. 3, No. 1, 1979, pp. 23-34. doi:10.1002/jgt.3190030104
- J. J. Bartholdi, J. B. Orlin and H. D. Ratliff, “Cyclic Scheduling via Integer Programs with Circular Ones,” Operations Research, Vol. 28, No. 5, 1980, pp. 1074- 1085. doi:10.1287/opre.28.5.1074
- W. Dauscha, H. D. Modrow and A. Neumann, “On Cyclic Sequence Type for Constructing Cyclic Schedules,” Zeitschrift für Operations Research, Vol. 29, No. 1, 1985, pp. 1-30.
- D. de Werra, N. V. R. Mahadev and P. Solot, “Periodic Compact Scheduling,” ORWP 89/18, Ecole Polytechnique Fédérale de Lausanne, 1989.
- D. de Werra and Ph. Solot, “Compact Cylindrical Chromatic Scheduling,” ORWP 89/10, Ecole Polytechnique Fédérale de Lausanne, 1989.
- R. R. Kamalian, “On Cyclically Continuous Edge Colorings of Simple Cycles,” Proceedings of the Computer Science and Information Technologies Conference, Yerevan, 24-28 September 2007, pp. 79-80. (in Russian)