A bipartite graph G is called (α,β)-biregular if all vertices in one part of G have degree α and all vertices in the other part have degree β. An edge coloring of a graph G with colors 1,2,3,…,t is called an interval t-coloring if the colors received by the edges incident with each vertex of G are distinct and form an interval of integers and at least one edge of G is colored i, for i=1,…,t. We show that the problem to determine whether an (α,β)-biregular bipartite graph G has an interval t-coloring is NF-complete in the case when α=6, β=3 and t=6. It is known that if an (α,β)-biregular bipartite graph G on m vertices has an interval t-coloring then α+β-gcd(α,β)≤t≤m-1, where gcd(α,β) is the greatest common divisor of α and β. We prove that if an (α,β)-biregular bipartite graph has m≥2(α+β) vertices then the upper bound can be improved to m-3.
展开▼
