INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES

Authors

  • Albert Kh. Sahakyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
  • Rafayel R. Kamalian Chair of Information Technologies and Applied Mathematics of European University of Armenia, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2021.55.2.113

Keywords:

trees, interval t-coloring, interval edge coloring, restrictions on edges, dynamic programming, bipartite matching

Abstract

An edge-coloring of a graph $G$ with consecutive integers $c_1,\ldots,c_t$ 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 of the tree and provide a polynomial algorithm for checking interval colorability that satisfies those restrictions.

Downloads

Published

2021-08-30

How to Cite

Sahakyan, A. K., & Kamalian, R. R. (2021). INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES. Proceedings of the YSU A: Physical and Mathematical Sciences, 55(2 (255), 113–122. https://doi.org/10.46991/PYSU:A/2021.55.2.113

Issue

Section

Mathematics