Гипотеза Хедетниеми
В теории графов гипотеза Хедетниеми , сформулированная Стивеном Т. Хедетниеми в 1966 году, касается связи между раскраской графа и тензорным произведением графов . Эта гипотеза утверждает, что
Здесь обозначает хроматическое число неориентированного конечного графа .
Неравенство χ( G × H ) ⩽ min {χ( G ), χ( H )} просто: если G k -раскрашена, то можно k -раскрасить G × H , используя одну и ту же раскраску для каждой копии G в продукт; симметрично, если H k -цветная . Таким образом, гипотеза Хедетниеми сводится к утверждению, что тензорные произведения нельзя раскрасить неожиданно малым числом цветов.
Контрпример к гипотезе обнаружил Ярослав Шитов ( 2019 ) (см. Калай 2019 ), тем самым опровергнув гипотезу в целом.
Любой граф с непустым набором ребер требует как минимум двух цветов; если G и H не являются 1-раскрашиваемыми, т. е. оба содержат ребро, то их произведение также содержит ребро и, следовательно, также не является 1-раскрашиваемым. В частности, гипотеза верна, когда G или H — двудольный граф, так как тогда его хроматическое число равно 1 или 2.
Аналогично, если два графа G и H не являются 2-раскрашиваемыми, то есть не двудольными , то оба содержат цикл нечётной длины. Поскольку произведение двух графов с нечетными циклами содержит нечетный цикл, произведение G × H также не является 2-раскрашиваемым. Другими словами, если G × H раскрашивается в 2 цвета, то по крайней мере один из G и H также должен быть раскрашиваем в 2 цвета.
