主題
Search

圖洞


Chvátal 將術語“洞”定義為“長度至少為四的無弦圈”。“長度至少為四”的限制允許使用術語“洞”,而無需考慮“無弦圈”的定義是否已經排除長度為 3 的圈(例如,West 2002, p. 225)或將其包括在內(Cook 2012, p. 197; Wikipedia)。

如果圖洞具有偶數個頂點,則稱為偶洞;如果具有奇數個頂點,則稱為奇洞。圖洞的圖補稱為圖反洞。沒有奇洞是完美圖(因為奇洞的團數為 2,其色數為 3)。


另請參閱

Berge 圖, 無弦圈, 圖反洞, 圖圈, 強完美圖定理

使用 探索

參考文獻

Chvátal, V. "強完美圖定理。" http://www.cs.concordia.ca/~chvatal/perfect/spgt.htmlCook, K.; Eschen, E. M.; Sritharan, R.; 和 Wang, X. "完成著色圖以滿足目標屬性。" 收錄於 計算機科學中的圖論概念:第 39 屆國際研討會,WG 2013,德國呂貝克,2013 年 6 月 19-21 日,修訂論文集。 Ed. A. Brandstädt, K. Jansen, 和 R. Reischuk)。德國柏林:â-¢Springer,pp. 189-200, 2013。West, D. B. 圖論導論,第 2 版。 Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000。Wikipedia 貢獻者。 "匯出路徑。" 維基百科,自由的百科全書。維基百科,自由的百科全書。 2020 年 8 月 7 日;檢索於 2020 年 9 月 4 日。 https://en.wikipedia.org/wiki/Induced_path

在 中被引用

圖洞

請引用為

Weisstein, Eric W. "圖洞。" 來自 —— 資源。 https://mathworld.tw/GraphHole.html

主題分類