L-Coloring with impropriety d: различия между версиями

'''<math>\,L</math>-Coloring with impropriety <math>d</math>''' — ''[[L-Раскраска с некорректностью d|<math>\,L</math>-раскраска с некорректностью <math>\,d</math>]].''

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

 

 

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