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.

A graph G is called interval colorable if it has a proper edge coloring with colors 1,2,3,… such that the colors of the edges incident to every vertex of G form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph G, denoted θint(G), which is the minimum number of interval colorable edge-disjoint subgraphs of G whose union is G. Our investigation is motivated by scheduling problems with compactness requirements, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly 3-edge colorable graph with maximum degree 3 is interval colorable, and using this result, we deduce an upper bound on θint(G) for general graphs G. We demonstrate that this upper bound can be improved in the case when G is bipartite, planar or complete multipartite and consider some applications in timetabling.

A k-improper edge coloring of a graph G is a mapping α:E(G)⟶N such that at most k edges of G with a common endpoint have the same color. An improper edge coloring of a graph G is called an improper interval edge coloring if the colors of the edges incident to each vertex of G form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph G defined as the smallest k such that G has a k-improper interval edge coloring; we denote the smallest such k by μint(G). We prove upper bounds on μint(G) for general graphs G and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine μint(G) exactly for G belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer k, there exists a graph G with μint(G)=k. Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring.