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

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

править

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

 

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

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

править

Более слабая форма гипотезы, доказанная М. Шефером[4], утверждает, что любой граф с хроматическим числом n имеет число пересечений Ω(n4), или, эквивалентно, что любой граф с числом пересечений k имеет хроматическое число O(k1/4). Алберсон, Крэтсон и Фокс[4] опубликовали доказательство этих границ путём комбинации факта, что любой минимальный n-хроматический граф имеет минимальную степень, не меньшую   (в противном случае можно было бы раскрасить его в   цветов после удаления вершины с малой степенью, раскраски оставшегося графа и использования доступного цвета для удалённой вершины, что противоречит минимальности графа) вместе с неравенством для числа пересечений, согласно которому любой граф   с   имеет число пересечений  ). Используя те же доводы, они показывают, что контрпример гипотезе Албертсона с хроматическим числом n (если таковой существует) должен иметь менее 4 n вершин.

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

править

Гипотеза Албертсона является не имеющим содержания истинным утверждением[англ.] для   —   имеет число пересечений нуль и все графы имеют число пересечений, не меньшее нуля. Случай   гипотезы Албертсона эквивалентен теореме о чётырёх красках, что любой планарный граф может быть раскрашен в четыре или меньше цветов, а единственные графы, для которых требуется меньше пересечений, чем у графа K5, это планарные графы, по гипотезе же они должны быть не более чем 4-хроматическими. Благодаря поддержке некоторых групп авторов сейчас известно, что гипотеза верна для всех  [5][4][6]. Для любого целого числа   Луис и Рихтер представили семейства (c+1)-критических по цвету графов, которые не содержат подразделения полного графа K(c+1), но имеющие число пересечений, не меньшее K(c+1)[7].

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

править

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

Примечания

править
  1. Согласно Албертсону, Кранстону и Фоксу(Albertson, Cranston, Fox 2009) гипотеза была сделана Албертсоном на специальной сессии Американского математического общества в Чикаго, состоявшейся в октябре 2007.
  2. Hutchinson, 2009.
  3. Guy, 1972.
  4. 1 2 3 4 Albertson, Cranston, Fox, 2009.
  5. Oporowski, Zhao, 2009.
  6. 1 2 Barát, Tóth, 2010.
  7. Luiz, Richter, 2014.
  8. Catlin, 1979.
  9. Erdős, Fajtlowicz, 1981.

Литература

править
  • Joan P. Hutchinson. In memory of Michael O. Albertson, 1946–2009: a collection of his outstanding conjectures and questions in graph theory. — SIAM Activity group on Discrete Mathematics, 2009.
  • Michael O. Albertson, Daniel W. Cranston, Jacob Fox. Colorings, crossings, and cliques // Electronic Journal of Combinatorics. — 2009. — Т. 16. — С. R45. — arXiv:1006.3783..
  • János Barát, Géza Tóth. Towards the Albertson Conjecture // Electronic Journal of Combinatorics. — 2010. — Т. 17, вып. 1. — С. R73. — arXiv:0909.0413..
  • Catlin P. A. Hajós's graph-colouring conjecture: variations and counterexamples // Journal of Combinatorial Theory, Series B. — 1979. — Т. 26, вып. 2. — С. 268–274. — doi:10.1016/0095-8956(79)90062-5..
  • Paul Erdős, Siemion Fajtlowicz. On the conjecture of Hajós // Combinatorica. — 1981. — Т. 1, вып. 2. — С. 141–143. — doi:10.1007/BF02579269..
  • Richard K. Guy. Crossing numbers of graphs // Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10–13, 1972 / Y. Alavi, D. R. Lick, A. T. White. — New York: Springer-Verlag, 1972. — С. 111–124.. Как процитировано в статье Албертсона, Крэнстона и Фокса(Albertson, Cranston & Fox 2009)
  • Oporowski B., Zhao D. Coloring graphs with crossings // Discrete Mathematics. — 2009. — Т. 309, вып. 9. — С. 2948–2951. — doi:10.1016/j.disc.2008.07.040. — arXiv:math/0501427.
  • Atílio Luiz, Bruce Richter. Remarks on a conjecture of Barát and Tóth // Electronic Journal of Combinatorics. — 2014. — Т. 21, вып. 1. — С. P1.57.