Звездно-хроматическое число: различия между версиями

'''Звездно-хроматическое число''' (''[[Star-chromatic number]]'') — Пусть <math>\,k</math> и <math>\,d</math> — натуральные числа, <math>k \geq 2d</math>. [[(k,d)-Раскраска|<math>\,(k,d)</math>-'''раскраской''']] [[граф|графа]] <math>\,G=(V,E)</math> называется отображение <math>c: \; V \longrightarrow Z_{k} = \{0,,1,..., k-1\}</math> такое, что для каждого [[ребро|ребра]] <math>uv \in E</math> <math>|c(u) - c(v)|_{k} \geq d</math>, где <math>\,|x|_{k} = \min\{|x|, k - |x|\}</math>. Это обобщает обычное понятие [[раскраска|раскраски]]. '''Звездно-хроматическое число'''

<math>\chi^{\star}(G)</math> есть наименьшее <math>\, k/d</math>, при котором граф имеет <math>\,(k,d)</math>-раскраску. Известно, что [[хроматическое число]] графа определяется его звездно-хроматическим числом, но обратное неверно.

* [Discrete Math.]