An interval edge coloring of a graph is a proper edge coloring by integers such that the colors on the edges incident with any vertex form an interval of integers. Not all graphs are interval colorable; a simple counterexample is K 3 . A near-interval coloring is a proper edge coloring of a graph such that the colors on the edges incident with any vertex is either an interval or a near-interval , where the latter is an interval except for one missing integer. We prove that all graphs of maximum degree at most 4, and all Class 1 graphs of maximum degree 5 and no vertices of degree 3 are near-interval colorable, thereby improving previous results by Petrosyan et al. (2010). We also consider the problem of near-interval coloring outerplanar graphs. For bipartite graphs , we prove that every such multigraph of maximum degree at most 5 admits a near-interval coloring, and that for every Δ ≥ 18 there is a bipartite graph of maximum degree Δ with no near-interval coloring. For the case of bipartite multigraphs, we give analogous examples of graphs of maximum degrees Δ with no near-interval coloring for every Δ ≥ 15 . Finally, we present classes of bipartite multigraphs of maximum degree 6,7 and 8 that admit near-interval colorings.

An edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular if each vertex in one part has degree α and each vertex in the other part has degree β. A graph G is called (α*,β*)-bipartite if G is a subgraph of an (α,β)-biregular graph and the maximum degree in one part is α and the maximum degree in the other part is β. In the paper we study the problem of interval edge colorings of (k*,2*)-bipartite graphs, for k ∈ {3,4,5}, and of (5*,3*)-bipartite graphs. We prove that every (5*,2*)-bipartite graph admits an interval edge coloring using at most 6 colors, which can be found in O(n^{3/2}) time, and we prove that an interval edge 5-coloring of a (5*,2*)-bipartite graph can be found in O(n^{3/2}) time, if it exists. We show that every (4^*,2^*)-bipartite graph admits an interval edge 4-coloring, which can be found in O(n) time. The two following problems of interval edge coloring are known to be NP-complete: 6-coloring of (6,3)-biregular graphs (Asratian and Casselgren (2006)) and 5-coloring of (5*,5*)-bipartite graphs (Giaro (1997)). In the paper we prove NP-completeness of 5-coloring of (5*,3*)-bipartite graphs.