New Search

Export article
Open Access

INTERVAL EDGE COLORING OF TREES WITH STRICT RESTRICTIONS ON THE SPECTRUMS

Albert Khachik Sahakyan
Published: 15 June 2021

Abstract: An edge-coloring of a graph G with consecutive integers C1 ,..., Ct is called an interval t-coloring if all the 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. For an edge coloring a and a vertex v the set of all the colors of the incident edges of v is called the spectrum of that vertex in a and is denoted by Sa(v). We consider the case where the spectrum for each vertex v is provided S(v), and the problem is to find an edge-coloring a such that for every vertex v, Sa(v)=S(v). We provide an O(N) algorithm that finds such an edge-coloring for trees that satisfies all the restrictions. If it is impossible to have an edge-coloring that satisfies the restrictions of the spectrums the algorithm will tell that too.
Keywords: edge coloring / graph / integers / COLORING OF TREES / satisfies / STRICT

Scifeed alert for new publications

Never miss any articles matching your research from any publisher
  • Get alerts for new papers matching your research
  • Find out the new papers from selected authors
  • Updated daily for 49'000+ journals and 6000+ publishers
  • Define your Scifeed now

Share this article

Click here to see the statistics on "Science Review" .
References (4)
    Back to Top Top