NEAR-INTERVAL EDGE-COLORINGS OF COMPLETE BIPARTITE GRAPHS

Abstract

A proper edge-coloring of a graph $G$ is a mapping $\alpha:E(G)\longrightarrow  \mathbb{N}$ such that $\alpha(e)\not=\alpha(e')$ for every pair of adjacent edges $e$ and $e'$ in $G$. If $\alpha $ is a proper edge-coloring of $G$ and $v\in V(G)$, then $S_{G}\left(v,\alpha \right)$ denotes the set of colors appearing on edges incident to $v$. A proper edge-coloring $\alpha$ of a graph $G$ with colors $1,\ldots,t$ is called a near-interval $t$-coloring if all colors are used, and for each vertex $v\in V(G)$, $S_G(v,\alpha)$ is an interval of integers with no more than one gap.  If a graph $G$ has such a coloring, the minimum number of colors in a near-interval coloring of a graph $G$ is denoted by $w^{1}(G)$. It is known that all complete bipartite graphs admit near-interval colorings. In this paper, we determine or bound the parameter $w^{1}(K_{m,n})$ ($m,n\in\mathbb{N}$) for complete bipartite graphs.