主题
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.net.cn/ChromaticallyUniqueGraph.html

主题分类