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].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.