Loading AI tools
З Вікіпедії, вільної енциклопедії
Гіпотеза Хадвігера — одна з нерозв'язаних гіпотез теорії графів . Вона формулюється так: будь-який k-хроматичний граф стягується до повного графу на вершинах.
Ця стаття не містить посилань на джерела. (липень 2024) |
Гіпотезу Хадвігера можна сформулювати інакше: у кожному -хроматичному графі обов'язково існує зв'язних підграфів, які не перетинаються і між будь-якими двома з них є ребро.
Якщо ввести для графу число Хадвігера — максимальне таке, що стягується до повного графу на вершинах, то гіпотеза формулюється у вигляді нерівності , де — хроматичне число графу.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.