Open AccessINTERVAL EDGE-COLORING OF COMPLETE AND COMPLETE BIPARTITE GRAPHS WITH RESTRICTIONS
Author(s) -
Sahakyan Albert,
Muradyan Levon
Publication year - 2021
Publication title -
world science/world science
Language(s) - English
Resource type - Journals
eISSN - 2414-6404
pISSN - 2413-1032
DOI - 10.31435/rsglobal_ws/30092021/7689
Subject(s) - combinatorics , edge coloring , bipartite graph , mathematics , complete coloring , graph coloring , complete bipartite graph , discrete mathematics , fractional coloring , interval graph , vertex (graph theory) , interval (graph theory) , list coloring , 1 planar graph , indifference graph , greedy coloring , chordal graph , graph , graph power , line graph
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.