INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES

Author(s)

INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES Albert Sahakyan

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 of the tree and provide a polynomial algorithm for checking interval colorability that satisfies those restrictions.

DOI: 10.46991/PYSU:A/2021.55.2.113 Physical and Mathematical Sciences, 55(2 (255) 113-122

Download PDF

Keywords

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

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]