主题
数学天地
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.net.cn/IsomorphicFactorization.html

主题分类