L-Coloring with impropriety d: различия между версиями
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>. | |||
Текущая версия от 13:46, 1 октября 2014
[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.