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