Звездно-экстремальный граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Звездно-экстремальный граф''' (''Star-extremal graph'') - граф <math>G</math> называется зве...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Звездно-экстремальный граф''' (''Star-extremal graph'') - | '''Звездно-экстремальный граф''' (''[[Star-extremal graph]]'') - [[граф]] <math>G</math> называется звездно-экстремальным, если его [[звездно-хроматическое число]] равно [[дробно-хроматическое число|дробно-хроматическому числу]], <math>\chi^{\star}(G) = \chi_{f}(G)</math>. Известно, что для [[лексикографическое произведение|лексикографического произведения]] <math>G[H]</math> графа <math>G</math> и произвольного графа <math>H</math> <math>\chi^{\star}(G[H])</math> равно произведению <math>\chi^{\star}(G)</math> и <math>\chi(H)</math>. | ||
граф <math>G</math> называется звездно-экстремальным, если его | |||
звездно-хроматическое число равно дробно-хроматическому числу, | |||
<math>\chi^{\star}(G) = \chi_{f}(G)</math>. Известно, что для лексикографического произведения <math>G[H]</math> | |||
графа <math>G</math> и произвольного графа | |||
<math>H</math> <math>\chi^{\star}(G[H])</math>равно произведению <math>\chi^{\star}(G)</math> и <math>\chi(H)</math>. | |||
==Литература== | ==Литература== | ||
[Discrete Math.] | [Discrete Math.] | ||
Версия от 11:17, 21 октября 2009
Звездно-экстремальный граф (Star-extremal graph) - граф [math]\displaystyle{ G }[/math] называется звездно-экстремальным, если его звездно-хроматическое число равно дробно-хроматическому числу, [math]\displaystyle{ \chi^{\star}(G) = \chi_{f}(G) }[/math]. Известно, что для лексикографического произведения [math]\displaystyle{ G[H] }[/math] графа [math]\displaystyle{ G }[/math] и произвольного графа [math]\displaystyle{ H }[/math] [math]\displaystyle{ \chi^{\star}(G[H]) }[/math] равно произведению [math]\displaystyle{ \chi^{\star}(G) }[/math] и [math]\displaystyle{ \chi(H) }[/math].
Литература
[Discrete Math.]