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
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
