主題
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 圖

使用 探索

參考文獻

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. "迴圈色數。" 來自 Web 資源。 https://mathworld.tw/CyclicChromaticNumber.html

主題分類