INTERVAL EDGE-COLORING OF COMPLETE AND COMPLETE BIPARTITE GRAPHS WITH RESTRICTIONS

Sahakyan Albert; Muradyan Levon

doi:10.31435/rsglobal_ws/30092021/7689

Sahakyan Albert Ph.D. Student, Chair of Discrete Mathematics and Theoretical Informatics, Faculty of Informatics and Applied Mathematics, Yerevan State University, Armenia
Muradyan Levon Master’s Student, Chair of Discrete Mathematics and Theoretical Informatics, Faculty of Informatics and Applied Mathematics, Yerevan State University, Armenia

DOI: https://doi.org/10.31435/rsglobal_ws/30092021/7689

Keywords: complete graph, complete bipartite graph, interval t-coloring, interval edge-coloring, restrictions on edges, NP-complete, bipartite matching

Abstract

An edge-coloring of a graph G with consecutive integers c1,…,ct is called an interval t-coloring, if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. In this paper, we consider the case where there are restrictions on the edges, and the edge-coloring should satisfy these restrictions. We show that the problem is NP-complete for complete and complete bipartite graphs. We also provide a polynomial solution for a subclass of complete bipartite graphs when the restrictions are on the vertices.

References

West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey, 1996.

Asratian A.S., KamalianR.R. Interval Colorings of Edges of a Multigraph. Appl. Math.5(1987), 25-34 (in Russian).

Kamalian R.R. Interval Colorings of Complete Bipartite Graphs and Trees. Preprint of the Computing Centre of the Academy of Sciences of Armenia. Yer. (1989).

Kamalian R.R. Interval Edge-colorings of Graphs. Doctoral Thesis. Novosibirsk (1990).

Axenovich M.A. On interval colorings of planar graphs. Congr. Numer.159(2002) 77–94.

Kamalian R.R., Petrosyan P.A. A note on interval edge-colorings of graphs. Math. Probl. Comput. Sci.36(2012) 13–16.

Petrosyan P.A. Interval edge-colorings of complete graphs and n-dimensional cubes. Discrete Math.310(2010) 1580–1587. Retrieved from https://doi.org/10.1016/j.disc.2010.02.001

Petrosyan P.A., Khachatrian H.H., Tananyan H.G. Interval edge-colorings of Cartesian products of graphs I. Discuss. Math. Graph Theory 33 (2013) 613–632. Retrieved from https://doi.org/10.7151/dmgt.1693

Khachatrian H. H., Petrosyan P. A. Interval edge-colorings of complete graphs. Discrete Mathematics, 339(9), (2016) 2249–2262. Retrieved from https://doi.org/10.1016/j.disc.2016.04.002

Kamalian R. R., Petrosyan, P. A. On Lower Bound for W(К2n). Mathematical Problems of Computer Science, Vol. 23, (2004), pp. 127-129.

Kamalian R.R., Petrosyan P.A., On interval edge colorings of Harary graphs H2n−2,2n. Mathematical Problems of Computer Science, Vol. 24, (2005), pp. 86-88.

Kamalian R. R., Petrosyan P. A. On Interval Colorings of Complete k-partite Graphs Knk. Mathematical Problems of Computer Science, Vol. 26, (2006), pp. 28-32.