# On Interval-Separable Subsets of Vertices of a Complete Graph

## Abstract

A subset R of the set of vertices of a graph G is called interval-separable if there exists a proper edge coloring of G in which colors of edges incident with any vertex x of G form an interval of integers if xR . All interval-separable subsets of the set of vertices of the complete graph are found.

## References

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

V.G. Vizing, The chromatic index of a multigraph, Kibernetika 3, pp. 29-39, 1965.

A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math 5, Yerevan State University, pp 25-34, 1987.

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, 103 p., 1990.

R.R. Kamalian, P.A. Petrosyan, On lower bound for W(K2n), Mathematical Problems of Computer Science, Vol. 23, pp 127-129, Yerevan, 2004.

P.A. Petrosyan, Interval color–feasible sequences for some classes of graphs, PhD thesis, Institute for Informatics and Automation Problems of NAS of RA, Yerevan, 130 p., 2006.

R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, Preprint of the Computing Centre of the Academy of Sciences of Armenia, 11p, 1989.

## Downloads

## Published

## How to Cite

*Mathematical Problems of Computer Science*,

*31*, 108–115. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/397