主题
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)。


另请参阅

牛图, 色多项式, 由谱确定, 同构图

使用 Wolfram|Alpha 探索

参考文献

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 "整数序列在线百科全书"。

Wolfram|Alpha 参考

色唯一图

请引用为

Weisstein, Eric W. "色唯一图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ChromaticallyUniqueGraph.html

主题分类