Граф Эллингема — Хортона

Графы Эллингема — Хортона — два 3-регулярных графа с 54 и 78 вершинами — 54-граф Эллингема — Хортона и 78-граф Эллингема — Хортона. Графы названы именами Джозефа Хортона и Марка Эллингема, которые их открыли. Эти два графа дают контрпримеры гипотезе Уильяма Татта о том, что каждый кубический 3-связный двудольный граф является гамильтоновым.

Первым контрпримером гипотезы Татта был граф Хортона, который опубликовали Бодни и Мёрти. После графа Хортона было найдено несколько меньших контрпримеров гипотезе Татта. Среди них находятся 92-вершинный граф Хортона, 78-вершинный граф Овенса и два графа Эллингема — Хортона.

Первый граф Эллингема — Хортона опубликовал Эллингем и он имеет порядок 78. В то время граф был наименьшим известным контрпримером гипотезе Татта. Второй граф Эллингема — Хортона опубликовали Эллингем и Хортон и он имеет порядок 54. В 1989 был открыт на настоящее время наименьший негамильтонов 3-связный кубический двудольный граф Жоржа, содержащий 50 вершин.

Галерея

• Хроматическое число 54-графа Эллингема — Хортона равно 2.

• Хроматический индекс 54-графа Эллингема — Хортона равен 3.

• Хроматическое число 78-графа Эллингема — Хортона равно 2.

• Хроматический индекс 78-графа Эллингема — Хортона равен 3.