2020/03/13 by Carl Johan Casselgren, Petros A. Petrosyan, Casselgren, Carl Johan +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2003.06166
arxiv created 2020/03/13 · arxiv updated 2020/03/16
A k-improper edge coloring of a graph G is a mapping α:E(G)\longrightarrow ℕ 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.