主題
Search

同構因子分解


同構因子分解使用 顏色 對給定圖 G 的邊進行著色,使用 k 種顏色,使得著色後的 子圖同構 的。圖 G 於是是 k-可分的,其中 k 是除數,子圖是因子。

當一個 完全圖 被 2-分時,會得到一個 自補圖。類似地,一個 n-正則 1 類圖 可以被 n-分成分散的邊的圖,使得 n 成為 邊色數

完全圖 K_9 可以被 3-分成分解為相同的 平面圖

一些 拉姆齊數 已經透過同構因子分解被限定界限。例如,完全圖 K_(16)克萊布什圖 作為因子,證明了 R(3,3,3)>16 (Gardner 1989)。也就是說,在 16 個點的完全圖上可以進行三著色,使得不會出現單色的三角形。(在 1955 年,R(3,3,3)=17 被證明。)

IsomorphicFactorization

此外,K_(16) 可以被 8-分,以 彼得森圖 作為因子,或被 5-分,以加倍的 立方圖 作為因子(由 Exoo 在 2005 年證明)。

霍夫曼-辛格爾頓圖 是 7-可分分解為邊的(由 Royle 在 2004 年證明)。霍夫曼-辛格爾頓圖是否透過另一個 7-分成為 K_(50) 的因子,這是一個 未解決的問題


另請參閱

完全圖, 邊著色, 同構圖

此條目由 Ed Pegg, Jr. 貢獻 (作者連結)

使用 探索

參考文獻

Farrugia, A. "自補圖與推廣:綜合參考手冊。" 碩士論文。University of Malta, 1999. http://members.lycos.co.uk/afarrugia/sc-graph/sc-graph-survey.ps.Gardner, M. "拉姆齊理論。" Ch. 17 in 彭羅斯瓷磚與活板門密碼...以及矩陣博士的迴歸,再版。 New York: W. H. Freeman, pp. 231-247, 1989.West, D. "K_(50) 的霍夫曼-辛格爾頓分解。" http://www.math.uiuc.edu/~west/openp/hoffsing.html.

在 中被引用

同構因子分解

請引用為

Pegg, Ed Jr. "同構因子分解。" 來自 Web 資源,由 Eric W. Weisstein 建立。 https://mathworld.tw/IsomorphicFactorization.html

主題分類