ﻻ يوجد ملخص باللغة العربية
A $k$-improper edge coloring of a graph $G$ is a mapping $alpha:E(G)longrightarrow mathbb{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_{mathrm{int}}(G)$. We prove upper bounds on $mu_{mathrm{int}}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $mu_{mathrm{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_{mathrm{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.
A proper edge-coloring of a graph $G$ with colors $1,ldots,t$ is called an emph{interval cyclic $t$-coloring} if all colors are used, and the edges incident to each vertex $vin V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$, where $d_{
An edge-coloring of a graph $G$ with consecutive integers $c_{1},ldots,c_{t}$ is called an emph{interval $t$-coloring} if all colors are used, and the colors of edges incident to any vertex of $G$ are distinct and form an interval of integers. A grap
A proper edge coloring of a graph $G$ with colors $1,2,dots,t$ is called a emph{cyclic interval $t$-coloring} if for each vertex $v$ of $G$ the edges incident to $v$ are colored by consecutive colors, under the condition that color $1$ is considered
An edge-coloring of a graph $G$ with colors $1,2,ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if i
An emph{interval $t$-coloring} of a multigraph $G$ is a proper edge coloring with colors $1,dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors. A emph{cyclic interval $t$-coloring} of a multigr