主題
Search

色唯一圖


P(G) 表示有限簡單圖 G色多項式。如果 G 滿足: 當 P(G)=P(H) 意味著 GH同構圖,則稱 G 是色唯一的;換句話說,如果 G 由其色多項式確定。如果 GH 是非同構的但具有相同的 色多項式,則稱它們是 色等價的

圈圖是色唯一的 (Chao and Whitehead 1978),圖蘭圖也是 (Chao and Novacky 1982)。

色非唯一的著名圖包括 3- 和 4-槓鈴圖雙縫立方體牛圖爪圖,3-火柴棍圖Moser 錠子,2-謝爾賓斯基墊片圖星圖三面體四面體圖,以及 6- 和 8-輪圖

節點數為 n 的色非唯一簡單圖的數量,當 n=1, 2, ... 時,分別為 0, 0, 0, 4, 18, 115, 905, 11642, 267398, ... (OEIS A137567);而色唯一圖的相應數量分別為 1, 2, 4, 7, 16, 41, 139, 704, 7270, ... (OEIS A137568)。


另請參閱

牛圖, 色多項式, 由譜確定, 同構圖

使用 探索

參考文獻

Bari, R. A. "色等價圖。" In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 186-200, 1974.Chao, C.-Y. "唯一 N-可著色和色等價圖。" Bull. Malays. Math. Sci. Soc. 24, 3-103, 2001.Chao, C.-Y.; Guo, Z. Y.; and Li, N. Z. "色等價圖的一些族。" Bull. Malays. Math. Soc. 15, 77-82, 1992.Chao, C.-Y.; Guo, Z.-Y.; Li, N.-Z. "關於 q-圖。色多項式和相關主題 (上海, 1994)。" Discr. Math. 172, 9-16, 1997.Chao, C. Y. and Novacky, G. A. "關於最大飽和圖。" Disc. Math. 41, 139-143, 1982.Chao, C. Y. and Whitehead, E. G. Jr. "關於圖的色等價性。" In 圖論及其應用(國際會議論文集,西密歇根大學,卡拉馬祖,密歇根州,1976 年) (Ed. Y. Alavi and D. R. Lick). Berlin: Springer-Verlag, pp. 121-131, 1978.Frucht, R. W. and Giudici, R. E. "七個頂點的色唯一圖。" Ars Combin. A 16, 161-172, 1983.Koh, K. M. and Teo, K. L. "色唯一圖的搜尋。" Graphs Combin. 6, 259-285, 1990.Koh, K. M. and Teo, K. L. "色唯一圖的搜尋 II。" Disc. Math. 172, 59-78, 1997.Li, N.-Z.; Whitehead, E. G. Jr.; and Xu, S.-J. "具有二次 sigma-多項式的色唯一圖的分類。" J. Graph Th. 11, 169-176, 1987.Sloane, N. J. A. 序列 A137567A137568 in "整數序列線上百科全書"。

參考

色唯一圖

請引用為

Weisstein, Eric W. "色唯一圖。" 來自 Web 資源。 https://mathworld.tw/ChromaticallyUniqueGraph.html

主題分類