Microsoft Word - Tpelu.doc Mathematical Problems of Computer Science 31, 108--115, 2008. 108 On Interval-Separable Subsets of Vertices of a Complete Graph Hakob Z. Arakelyan1 and Rafayel R. Kamalian2 1Department of Informatics and Applied Mathematics, YSU, 2Institute for Informatics and Automation Problems of NAS of RA, e-mail: arak_hakob@yahoo.com, rrkamalian@yahoo.com Abstract A subset R of the set of vertices of a graph G is called interval-separable iff 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 iff x R . All interval-separable subsets of the set of vertices of the complete graph are found. References [1] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. [2] V.G. Vizing, The chromatic index of a multigraph, Kibernetika 3, pp. 29-39, 1965. [3] A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math 5, Yerevan State University, pp 25-34, 1987. [4] 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, 103p, 1990. [5] R.R. Kamalian, P.A. Petrosyan, On lower bound for W(K2n), Mathematical Problems of Computer Science, Vol.23, pp 127-129, Yerevan, 2004. [6] 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. [7] 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. ÈñÇí ·ñ³ýÇ ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý ÙÇç³Ï³Ûù³ÛÝáñ»Ý ³é³ÝÓݳóíáÕ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ Ù³ëÇÝ Ð. ²é³ù»ÉÛ³Ý è. ø³Ù³ÉÛ³Ý ²Ù÷á÷áõÙ G ·ñ³ýÇ ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý R »Ýóµ³½ÙáõÃÛáõÝÁ ÏáãíáõÙ ¿ ÙÇç³Ï³Ûù³ÛÝáñ»Ý ³é³ÝÓݳóíáÕ ³ÛÝ ¨ ÙdzÛÝ ³ÛÝ Å³Ù³Ý³Ï, »ñµ ·áÛáõÃÛáõÝ áõÝÇ G ·ñ³ýÇ ³ÛÝåÇëÇ ×Çßï ÏáÕ³ÛÇÝ Ý»ñÏáõÙ, áñ Ï³Ù³Û³Ï³Ý x ·³·³ÃÇÝ ÏÇó ÏáÕ»ñÇ ·áõÛÝ»ñÁ ϳ½ÙáõÙ »Ý µÝ³Ï³Ý Ãí»ñÇ µ³½ÙáõÃÛ³Ý Ù»ç ÙÇç³Ï³Ûù ³ÛÝ ¨ ÙdzÛÝ ³ÛÝ ¹»åùáõÙ, »ñµ x R : ¶ïÝí³Í »Ý ÉñÇí ·ñ³ýÇ ·³·³ÃÝ»ñÇ µ³½ÙáõÃÛ³Ý µáÉáñ ÙÇç³Ï³Ûù³ÛÝáñ»Ý ³é³ÝÓݳóíáÕ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÁ: Üϳñ³·ñí»É »Ý ³é³ç³ñÏí³Í ϳÝáÝÇ ÏÇñ³éáõÃÛ³Ý ³ñ¹Ûáõݳí»ïáõÃÛáõÝÁ óáõó³¹ñáÕ Ñ³Ù³å³ï³ëË³Ý å³ïÏ»ñÝ»ñ ¨ Ãí³ÛÇÝ ³ñ¹ÛáõÝùÝ»ñ: