В теории графов гипотеза Хедетниеми , сформулированная Стивеном Т. Хедетниеми в 1966 году, касается связи между раскраской графа и тензорным произведением графов . Эта гипотеза утверждает, что
Здесь обозначает хроматическое число неориентированного конечного графа .
Неравенство χ( G × H ) ≤ min {χ( G ), χ( H )} просто: если G является k -раскрашенным, можно k -раскрасить G × H , используя ту же самую раскраску для каждой копии G в произведении; симметрично, если H является k -раскрашенным. Таким образом, гипотеза Хедетниеми сводится к утверждению, что тензорные произведения не могут быть раскрашены неожиданно малым числом цветов.
Контрпример к этой гипотезе был обнаружен Ярославом Шитовым (2019) (см. Kalai 2019), тем самым опровергнув гипотезу в целом.
Любой граф с непустым множеством ребер требует по крайней мере двух цветов; если G и H не являются 1-раскрашиваемыми, то есть оба содержат ребро, то их произведение также содержит ребро и, следовательно, также не является 1-раскрашиваемым. В частности, гипотеза верна, когда G или H является двудольным графом, поскольку тогда его хроматическое число равно либо 1, либо 2.
Аналогично, если два графа G и H не являются 2-раскрашиваемыми, то есть не являются двудольными , то оба содержат цикл нечетной длины. Поскольку произведение двух нечетных графов циклов содержит нечетный цикл, произведение G × H также не является 2-раскрашиваемым. Другими словами, если G × H является 2-раскрашиваемым, то по крайней мере один из G и H также должен быть 2-раскрашиваемым.
Следующий случай был доказан намного позже утверждения гипотезы Эль-Захаром и Зауэром (1985): если произведение G × H является 3-раскрашиваемым, то одно из G или H также должно быть 3-раскрашиваемым. В частности, гипотеза верна, когда G или H является 4-раскрашиваемым (с тех пор неравенство χ( G × H ) ≤ min {χ( G ), χ( H )} может быть строгим только тогда, когда G × H является 3-раскрашиваемым). В остальных случаях оба графа в тензорном произведении являются по крайней мере 5-цветными, и прогресс был достигнут только для очень ограниченных ситуаций.
Следующая функция (известная как функция Поляка-Рёдля ) измеряет, насколько малым может быть хроматическое число произведений n -хроматических графов.
Гипотеза Хедетниеми тогда эквивалентна утверждению, что f ( n ) = n . Слабая гипотеза Хедетниеми вместо этого просто утверждает, что функция f ( n ) неограниченна. Другими словами, если тензорное произведение двух графов можно раскрасить несколькими цветами, это должно подразумевать некоторую границу хроматического числа одного из множителей.
Основной результат работы (Poljak & Rödl 1981), независимо улучшенный Польяком, Джеймсом Х. Шмерлем и Чжу, гласит, что если функция f ( n ) ограничена, то она ограничена не более чем 9. Таким образом, доказательство гипотезы Хедетниеми для 10-хроматических графов уже подразумевало бы слабую гипотезу Хедетниеми для всех графов.
Гипотеза изучается в более общем контексте гомоморфизмов графов , особенно из-за интересных связей с категорией графов (с графами как объектами и гомоморфизмами как стрелками). Для любого фиксированного графа K рассматриваются графы G , которые допускают гомоморфизм в K , записанный как G → K. Их также называют K -раскрашиваемыми графами. Это обобщает обычное понятие раскраски графов, поскольку из определений следует, что k -раскраска совпадает с K k -раскраской (гомоморфизмом в полный граф на k вершинах).
Граф K называется мультипликативным, если для любых графов G , H из того, что G × H → K , следует, что G → K или H → K. Как и в случае с классическими раскрасками, всегда верна обратная импликация: если G (или H , симметрично) является K -раскрашиваемым, то G × H легко K -раскрашивается, используя те же значения независимо от H. Тогда гипотеза Хедетниеми эквивалентна утверждению, что каждый полный граф является мультипликативным.
Вышеуказанные известные случаи эквивалентны утверждению, что K 1 , K 2 и K 3 являются мультипликативными. Случай K 4 широко открыт. С другой стороны, доказательство Эль-Захара и Зауэра (1985) было обобщено Хэггквистом и др. (1988), чтобы показать, что все графы циклов являются мультипликативными. Позднее Тардиф (2005) доказал в более общем виде, что все круговые клики K n/k с n/k < 4 являются мультипликативными. В терминах кругового хроматического числа χ c это означает, что если χ c ( G × H ) < 4 , то χ c ( G × H ) = min { χ c ( G ), χ c ( G )} . Врохна (2017) показал, что графы без квадратов являются мультипликативными.
Примеры не мультипликативных графов можно построить из двух графов G и H , которые не сравнимы в порядке гомоморфизма (то есть, ни G → H, ни H → G не выполняются). В этом случае, положив K = G × H , мы тривиально имеем G × H → K , но ни G, ни H не могут допускать гомоморфизма в K , поскольку в сочетании с проекцией K → H или K → G это дало бы противоречие.
Поскольку тензорное произведение графов является категориально-теоретическим произведением в категории графов (с графами в качестве объектов и гомоморфизмами в качестве стрелок), гипотезу можно перефразировать в терминах следующей конструкции на графах K и G. Экспоненциальный граф K G — это граф со всеми функциями V(G) → V(K) в качестве вершин (не только гомоморфизмов) и двумя функциями f , g , смежными, когда
В частности, существует петля в функции f (она смежна с собой) тогда и только тогда, когда функция задает гомоморфизм из G в K. Иначе говоря, существует ребро между f и g всякий раз, когда две функции определяют гомоморфизм из G × K 2 ( двудольное двойное покрытие G ) в K .
Экспоненциальный граф является экспоненциальным объектом в категории графов. Это означает, что гомоморфизмы из G × H в граф K соответствуют гомоморфизмам из H в K G . Более того, существует гомоморфизм eval : G × K G → K , заданный формулой eval( v , f ) = f ( v ) . Эти свойства позволяют сделать вывод, что мультипликативность K эквивалентна (El-Zahar & Sauer 1985) утверждению:
Другими словами, гипотезу Хедетниеми можно рассматривать как утверждение об экспоненциальных графах: для каждого целого числа k граф K k G либо k -раскрашиваем, либо содержит петлю (то есть G k -раскрашиваем ). Можно также рассматривать гомоморфизмы eval : G × K k G → K k как самые сложные случаи гипотезы Хедетниеми: если бы произведение G × H было контрпримером, то G × K k G также было бы контрпримером.
Обобщенная на направленные графы, гипотеза имеет простые контрпримеры, как заметили Поляк и Редль (1981). Здесь хроматическое число направленного графа является просто хроматическим числом базового графа, но тензорное произведение имеет ровно половину числа ребер (для направленных ребер g→g' в G и h→h' в H тензорное произведение G × H имеет только одно ребро, от (g,h) до (g',h') , в то время как произведение базовых неориентированных графов также имело бы ребро между (g,h') и (g',h) ). Однако слабая гипотеза Хедетниеми оказывается эквивалентной в направленных и ненаправленных настройках (Tardif & Wehlau 2006).
Проблема не может быть обобщена на бесконечные графы: Хайнал (1985) привел пример двух бесконечных графов, каждый из которых требует несчетного числа цветов, так что их произведение может быть раскрашено только счетным числом цветов. Рино (2013) доказал, что в конструируемой вселенной для каждого бесконечного кардинала существует пара графов с хроматическим числом, большим , так что их произведение все еще может быть раскрашено только счетным числом цветов.
Аналогичное равенство для декартового произведения графов было доказано Сабидусси (1957) и впоследствии переоткрыто несколько раз. Точная формула также известна для лексикографического произведения графов . Даффус, Сэндс и Вудроу (1985) представили две более сильные гипотезы, включающие уникальную раскрашиваемость.
