4624
правки
AlexM (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''<math>L</math>-Coloring with impropriety <math>d</math>''' - | '''<math>\,L</math>-Coloring with impropriety <math>d</math>''' — ''[[L-Раскраска с некорректностью d|<math>\,L</math>-раскраска с некорректностью <math>\,d</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 | 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>. | ||
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 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 | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
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>. |