On Interval-Separable Subsets of Vertices of a Complete Graph

Authors

  • Hakob Z. Arakelyan Yerevan State University
  • Rafayel R. Kamalian Institute for Informatics and Automation Problems of NAS RA

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 xR . 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

2008-09-25

How to Cite

Arakelyan, H. Z. ., & Kamalian, R. R. . (2008). On Interval-Separable Subsets of Vertices of a Complete Graph. Mathematical Problems of Computer Science, 31, 108–115. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/397

Most read articles by the same author(s)