主题
Search

循环色数


平面嵌入的循环着色是一种顶点着色,使得与同一面关联的顶点具有不同的颜色。图中循环着色所需的最小颜色数称为图的循环色数,通常表示为 chi_c (Plummer 和 Toft 1987, Zlámalová 2010) 或 chi^c (Borodin et al. 2007)。

Sanders 和 Zhao (2001) 证明了

 chi_c<=|_5/3Delta^*_|,

其中 Delta^* 是图的最大面度。符号 rho^* 有时用于代替 Delta^* (例如,Plummer 和 Toft 1987),q 也被使用 (例如,Tilley et al. 2024)。循环着色猜想是四色定理的重要扩展,四色定理指出:

 chi_c<=|_3/2Delta^*_|

(Borodin 1984, Plummer 和 Toft 1987, Tilley et al. 2024)。对于面完全平面嵌入,该猜想变为定理 (Chen et al. 1998, Tilley et al. 2024)。

据推测,对于多面体图chi_c<=q+2 (Plummer 和 Toft 1987, Horňák 和 Zlámalová 2010)。对于 n=1, 2, ... 的多面体图,其中 chi_c=q+2 的数量由 0, 0, 0, 0, 0, 1, 1, 3, 18, 129, ... 给出 (E. Weisstein,2024 年 9 月 3 日)。这些包括堆叠的 3-棱柱图。Plummer 和 Toft (1987) 注意到另外两个无限的此类图族,其中第一个在本工作中被称为 Plummer-Toft 图


另请参阅

色数, 平面嵌入, Plummer-Toft 图

使用 Wolfram|Alpha 探索

参考文献

Borodin, O. V. "平面图的顶点-面着色和 1-平面图着色的 Ringel 问题的解法。" Metody Diskret. Analiz. 41, 12-26, 1984.Borodin, O. V.; Sanders, D.; 和 Zhao, Y. "关于循环着色及其推广。" Disc. Math. 203, 23-40, 1999.Borodin, O. V.; Broersma, H. J.; Glebov, A.; 和 van den Heuvel, J. "循环色数的新上限。" J. Graph Th. 54, 58-72, 2007.Chen, Z.; Grigni, M.; 和 Papadimitiou, C. "平面地图图。" 在 Proc. 30th Symposium on Theory Computing, pp. 514-523, 1998.Enomoto, H.; Horňák, M.; 和 Jendrol', S. "3-连通平面图的循环色数。" SIAM J. Disc. Math. 14, 121-137, 2001.Horňák, M. 和 Zlámalová, J. "朝着证明 Plummer 和 Toft 的猜想迈出的又一步。" Disc. Math. 310, 442-452, 2010.Jensen, T. R. 和 Toft, B. 图着色问题。 纽约: Wiley, 1995.Ore, O. 和 Plummer, M. D. "平面图的循环着色。" 在 组合数学的最新进展,第三届滑铁卢组合数学会议论文集。 圣地亚哥,加利福尼亚州: Academic Press, pp. 287-293, 1969.Plummer, M. D. 和 Toft, B. "3-多面体的循环着色。" J. Graph Th. 11, 507-515, 1987.Sanders, D. P. "循环色数的新界限。" J. Combin. Th., Ser. B 83, 102-111, 2001.Sanders, D. P. 和 Zhao, Y. "循环色数的新界限。" J. Combin. Th., Ser. B 83, 102-111, 2001.Tilley, J.; Wagon, S.; 和 Weisstein, E. "面完全图的目录。" 2024 年 9 月 17 日。 https://arxiv.org/abs/2409.11249.Zlámalová, J. "关于循环色数的注释。" Discuss. Math. Graph Th. 30, 115-122, 2010.

请引用为

Weisstein, Eric W. "循环色数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CyclicChromaticNumber.html

主题分类