檢視艾林厄姆–霍頓圖的原始碼

在圖論的數學領域中，艾林厄姆-霍頓圖是指兩個分別有54和78個頂點的3-正則圖：艾林厄姆-霍頓54圖和艾林厄姆-霍頓78圖。這兩張圖以其發現者約瑟夫·D·霍頓和馬克·N·艾林厄姆的名字命名。這兩張圖為W·T·塔特的猜想提供了反例，該猜想稱所有三次3-連通二分圖都是漢米爾頓圖。艾林厄姆-霍頓54圖和艾林厄姆-霍頓78圖的書厚度為3，佇列數為2。

塔特猜想的第一個反例是霍頓圖，由...發表。在霍頓圖之後，又發現了一些更小的塔特猜想反例。其中包括由...提出的92頂點圖、由...提出的78頂點圖，以及這兩張艾林厄姆-霍頓圖。

第一張艾林厄姆-霍頓圖由...發表，階數為78。當時，它是已知最小的塔特猜想反例。第二張艾林厄姆-霍頓圖由...發表，階數為54。1989年，發現了喬治斯圖，這是目前已知最小的非漢米爾頓三次3-連通二分圖，含有50個頂點。

==圖庫==

File:Ellingham-Horton 54-graph 2COL.svg|艾林厄姆-霍頓54圖的著色數為2。
File:Ellingham-Horton 54-graph 3color edge.svg|艾林厄姆-霍頓54圖的著色指數為3。
File:Ellingham-Horton 78-graph 2COL.svg|艾林厄姆-霍頓78圖的著色數為2。
File:Ellingham-Horton 78-graph 3color edge.svg|艾林厄姆-霍頓78圖的著色指數為3。


==參考資料==

[[分類: 待校正]]