Near-interval edge colorings of graphs

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 K3. 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 triangle >= 18 there is a bipartite graph of maximum degree triangle with no nearinterval coloring. For the case of bipartite multigraphs, we give analogous examples of graphs of maximum degrees triangle with no near-interval coloring for every triangle >= 15. Finally, we present classes of bipartite multigraphs of maximum degree 6,7 and 8 that admit near-interval colorings. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).