On interval edge colorings of (α, β)-biregular bipartite graphs

A bipartite graph G is called (alpha, beta)-biregular if all vertices in one part of G have degree alpha and all vertices in the other part have degree fl. 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 (alpha, beta)-biregular bipartite graph G has an interval t-coloring is N P-complete in the case when alpha = 6, beta = 3 and t = 6. It is known that if an (alpha, beta)-biregular bipartite graph G on m vertices has an interval t-coloring then alpha + beta - gcd(alpha, beta) <= t <= m - 1, where gcd(alpha, beta) is the greatest common divisor of alpha and beta. We prove that if an (alpha, beta)-biregular bipartite graph has m >= 2(alpha + beta) vertices then the upper bound can be improved to m - 3. (c) 2006 Elsevier B.V. All rights reserved.