Колесо (теорія графів): відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 53:
[[Хроматичне число|Хроматичний многочлен]] колеса '''W<sub>n</sub>''' дорівнює:
<center><math>P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).</math></center>.
У теорії [[Матроїд|матроїдов]] є два особливо важливих виду матроідов — '''колеса''' і '''вихор''', і обидва види є похідними від графів-коліс. Матроїд '''k'''- колеса — це {{не перекладено | Графовий матроїд | графові матроїди ||graphic матроїдов}}колеса ''W''<sub>''k+1''</sub>, a
Колесо ''W''<sub>6</sub> дає приклад гіпотезі [[Ердешу, Пів|Підлоги Эрдеша]] у [[Теорія Рамсея|теорії Рамсея]] — він висловив припущення, що повний граф має найменше число Рамсея серед всіх графів з тим же хроматичним числом. Однак Фаудри і МакКей (Faudree, McKay, 1993) показали, що для ''W''<sub>6</sub> число Рамсея дорівнює 17, в той час як для повного графа ''K''<sub>4</sub>, з тим же хроматичним числом, число Рамсея дорівнює 18.
<ref>{{стаття
| |||