On interval edge-colorings of complete tripartite graphs
Andrzej Grzesik, Hrant Khachatrian · 2013
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 paper we prove that K1, m, nis 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.