Гипотеза Албертсона — недоказанная связь между числом пересечением и хроматическим числом графа . Гипотеза носит имя Михаила О. Албертсона, профессора колледжа Смит , который сформулировал утверждение в качестве гипотезы в 2007 . Гипотеза является одной из многих гипотез в теории раскраски графов . Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф K _n находится среди графов, имеющих наименьшее число пересечений. Эквивалентно, если граф может быть нарисован с меньшим числом пересечений, чем у K _n , тогда, согласно гипотезе, его можно раскрасить в меньше чем n цветов.

Гипотетическая формула минимального числа пересечений

Напрямую можно показать, что граф с ограниченным числом пересечений имеет ограниченное хроматическое число — можно назначить различные цвета концам всех пересекающихся рёбер и выкрасить в 4 цвета оставшийся после удаления этих рёбер планарный граф . Гипотеза Албертсона заменяет эту качественную связь между числом пересечений и числом цветов более точной количественной связью. Другая гипотеза Ричарда К. Гая утверждает, что число пересечений полного графа K _n равно

${\displaystyle {\textrm {cr}}(K_{n})={\frac {1}{4}}\left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor .}$

Известно, каким образом рисовать полные графы с таким числом пересечений, располагая вершины на двух концентрических окружностях. Что неизвестно, так это существуют ли рисунки с меньшим числом пресечений. Таким образом, усиленная формулировка гипотезы Албертсона гласит, что любой n -хроматический граф имеет число пересечений, не меньший правой части этой формулы . Эта усиленная гипотеза справедлива тогда и только тогда, когда обе гипотезы, гипотеза Гая и гипотеза Албертсона, верны.

Асимптотические границы

Более слабая форма гипотезы, доказанная М. Шефером , утверждает, что любой граф с хроматическим числом n имеет число пересечений Ω( n ⁴ ), или, эквивалентно, что любой граф с числом пересечений k имеет хроматическое число O ( k ^1/4 ). Алберсон, Крэтсон и Фокс опубликовали доказательство этих границ путём комбинации факта, что любой минимальный n -хроматический граф имеет минимальную степень, не меньшую ${\displaystyle n-1}$ (в противном случае можно было бы раскрасить его в ${\displaystyle (n-1)}$ цветов после удаления вершины с малой степенью, раскраски оставшегося графа и использования доступного цвета для удалённой вершины, что противоречит минимальности графа) вместе с неравенством для числа пересечений , согласно которому любой граф ${\displaystyle G=(V,E)}$ с ${\displaystyle |E|/|V|\geqslant 4}$ имеет число пересечений ${\displaystyle \Omega (|E|^{3}/|V|^{2}}$ ). Используя те же доводы, они показывают, что контрпример гипотезе Албертсона с хроматическим числом n (если таковой существует) должен иметь менее 4 n вершин.

Специальные случаи

Гипотеза Албертсона является для ${\displaystyle n\leqslant 4}$ — ${\displaystyle K_{4}}$ имеет число пересечений нуль и все графы имеют число пересечений, не меньшее нуля. Случай ${\displaystyle n=5}$ гипотезы Албертсона эквивалентен теореме о чётырёх красках , что любой планарный граф может быть раскрашен в четыре или меньше цветов, а единственные графы, для которых требуется меньше пересечений, чем у графа K ₅ , это планарные графы, по гипотезе же они должны быть не более чем 4-хроматическими. Благодаря поддержке некоторых групп авторов сейчас известно, что гипотеза верна для всех ${\displaystyle n\leqslant 16}$ . Для любого целого числа ${\displaystyle c\geqslant 6}$ Луис и Рихтер представили семейства (c+1) -критических по цвету графов, которые не содержат подразделения полного графа K _(c+1) , но имеющие число пересечений, не меньшее K _(c+1) .

Связанные гипотезы

Существует также связь с гипотезой Хадвигера , важной открытой проблеме комбинаторики, касающейся связи между хроматическим числом и существованием больших клик в качестве миноров графа . Вариант гипотезы Хадвигера, выдвинутый Дьёрдьем Хайошем , утверждает, что любой n -хроматический граф содержит подразделение K _n . Если бы гипотеза была верна, из неё вытекала бы гипотеза Албертсона, поскольку число пересечений полного графа не меньше числа пересечений подразделения. Однако в настоящее время известны контрпримеры гипотезе Хайоша , так что эта связь не даёт возможности доказательства гипотезы Албертсона.

Примечания

Литература