Interval edge-colorings of K1,m,n

An edge-coloring of a graph G with colors 1,..., t is an interval t-coloring if all colors are used, and the colors of edges incident to each 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 note we prove that K1,m,n is interval colorable if and only if gcd(m+ 1, n+ 1) = 1, where gcd(m+ 1, n+ 1) is the greatest common divisor of m+ 1 and n+ 1. It settles in the affirmative a conjecture of Petrosyan. 1