主題
Search

停用次子圖

如果一個圖作為一個給定圖的次子圖出現，並導致該圖不屬於某個圖族，則該圖被稱為停用次子圖。

更一般地，可能存在一個次子圖族，它們的出現可以表徵一個給定的圖是否具有某種性質。例如，平面圖是一個不包含完全圖 K_5 或效用圖 K_(3,3) 作為次子圖的圖。下表總結了一些具有停用次子圖障礙的簡單圖族。

圖族障礙
頂點圖未知的有限數量的次子圖；至少已知 157 個
森林C_3
無連結可嵌入圖7 個 Petersen 圖族 停用次子圖
外平面圖K_4 和 K_(2,3)
路徑寬度 <=1C_3 和 (3,2)-輻條圖
路徑寬度 <=2110 個停用次子圖
平面圖K_5 和 K_(3,3)
射影平面圖35 個停用次子圖
環面圖未知的有限數量的次子圖；已知數千個
樹寬度 <=2K_4
樹寬度 <=3K_5, 八面體圖 K_(2,2,2), 稜柱圖 P_2 平方 C_5, 瓦格納圖 M_4
樹寬度 <=4未知的有限數量的次子圖；至少已知 75 個

另請參閱

停用匯出子圖, 停用子圖, 停用拓撲次子圖, Kuratowski 歸約定理, 無連結可嵌入圖, 外平面圖, 射影平面圖, 平面圖, Robertson-Seymour 定理, Wagner 定理

使用 探索

參考文獻

Peirce, M. "Minor-Minimal Graph Functions." https://github.com/mikepierce/MMGraphFunctions.

請按如下方式引用

Weisstein, Eric W. "停用次子圖。" 來自 —— 資源。 https://mathworld.tw/ForbiddenMinor.html

主題分類