Improper interval edge colorings of graphs

A k-improper edge coloring of a graph G is a mapping alpha : 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 mu(int)(G). We prove upper bounds on mu(int)(G) for general graphs G and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine mu(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 mu(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. (C) 2021 The Author(s). Published by Elsevier B.V.