Граф Хортона

После публикации графа Хортона были найдены некоторые другие меньшие контрпримеры Татта. Среди них — граф с 92 вершинами, опубликованный Хортоном в 1982, граф с 78 вершинами, который опубликовал Оуэнс в 1983, и два графа Эллингема – Хортона (с 54 и 78 вершинами)[4][5].

Первый граф Эллингема – Хортона был опубликован Эллингемом в 1981 и имел 78 вершин[6]. В то время это был самый маленький известный контрпример гипотезе Татта. Второй граф был опубликован Эллингемом и Хортоном в 1983 и он имеет 54 вершин[7]. Никаких меньших негамильтоновых кубических 3-связных двудольных графов в настоящее время не известно.

Поскольку граф Хортона, не являясь гамильтоновым, имеет много длинных циклов, он является хорошей тестовой базой для программ поиска гамильтоновых циклов[8].

Граф Хортона имеет хроматическое число 2, хроматический индекс 3, радиус 10, диаметр 10 и обхват 6. Он также является рёберно 3-связным графом.

Группа автоморфизмов графа Хортона имеет порядок 96 и изоморфна Z/2Z×Z/2Z×S₄, прямому произведению четверной группы Клейна и симметрической группы S₄.

Характеристический многочлен графа Хортона равен ${\displaystyle (x-3)(x-1)^{14}x^{4}(x+1)^{14}(x+3)(x^{2}-5)^{3}(x^{2}-3)^{11}(x^{2}-x-3)(x^{2}+x-3)}$ ${\displaystyle (x^{10}-23x^{8}+188x^{6}-644x^{4}+803x^{2}-101)^{2}}$ ${\displaystyle (x^{10}-20x^{8}+143x^{6}-437x^{4}+500x^{2}-59)}$.

• 
  Хроматическое число графа Хортона равно 2.
• 
  Хроматический индекс графа Хортона равен 3.
• 
  Граф Эллингема — Хортона, наименьший контрпример гипотезы Татта.