L-Coloring with impropriety d

[math]\displaystyle{ L }[/math]-Coloring with impropriety [math]\displaystyle{ d }[/math] --- [math]\displaystyle{ L }[/math]-раскраска с некорректностью [math]\displaystyle{ d }[/math].

A list assignment of [math]\displaystyle{ G }[/math] is a function [math]\displaystyle{ L }[/math] which assigns a list of colors [math]\displaystyle{ L(v) }[/math] to each vertex [math]\displaystyle{ v \in V(G) }[/math]. An [math]\displaystyle{ L }[/math]-coloring with impropriety [math]\displaystyle{ d }[/math], or simply [math]\displaystyle{ (L,d)* }[/math]-coloring, is a mapping [math]\displaystyle{ \lambda }[/math] which assigns to each vertex [math]\displaystyle{ v \in V(G) }[/math] a color [math]\displaystyle{ \lambda(v) }[/math] from [math]\displaystyle{ L(v) }[/math] so that [math]\displaystyle{ v }[/math] has at most [math]\displaystyle{ d }[/math] neighbours colored with [math]\displaystyle{ \lambda(v) }[/math]. For [math]\displaystyle{ m \in N }[/math], the graph is [math]\displaystyle{ m }[/math]-choosable with impropriety [math]\displaystyle{ d }[/math], or simply [math]\displaystyle{ (m,d)* }[/math]-choosable, if there exists an [math]\displaystyle{ (L,d)^{\ast} }[/math]-coloring for every list assignment [math]\displaystyle{ L }[/math] with [math]\displaystyle{ |L(v)| \geq m }[/math] for each [math]\displaystyle{ v ''V(G) }[/math]. For an improper coloring of a graph [math]\displaystyle{ G }[/math], the number of neighbours of [math]\displaystyle{ v \in V(G) }[/math] colored with the same color as itself is called the impropriety of [math]\displaystyle{ v }[/math] and is denoted by [math]\displaystyle{ im(v) }[/math]. The smallest [math]\displaystyle{ m }[/math] for which [math]\displaystyle{ G }[/math] is [math]\displaystyle{ (m,d)^{\ast} }[/math]-choosable is called the [math]\displaystyle{ d }[/math]-improper list chromatic number of [math]\displaystyle{ G }[/math] and is denoted by [math]\displaystyle{ \chi_{l}^{\ast}(G,d) }[/math].