星图Sn+1三类组合图的色等价性研究

"该文章是2009年发表在《青海师范大学学报(自然科学版)》第29卷第1期的一篇自然科学论文，作者是巩乐天和张秉儒，主要探讨了图的色等价性问题，特别是通过星图Sn+1的三类组合图进行分析。文章提出了利用图的伴随多项式的因式分解来研究图的色等价性的方法，并得出了相关组合图的色等价关系。" 正文: 色等价性是图论中的一个重要概念，它涉及图的染色问题。在图论中，一个图可以被染色，即给图的每个顶点分配一种颜色，使得相邻的顶点不具有相同的颜色。色等价性是指两个图可以通过某种颜色映射，使得它们的最小染色数相同，即两图都可用同样数量的颜色进行染色，而无需调整颜色分配。 该论文的主要目的是深入研究图的色等价性。作者通过分析星图Sn+1的三类组合图来探讨这个问题。星图是一种特殊的图，由一个中心顶点和n个与之相连的边构成，形状类似星星。在这里，作者考虑的是星图加上一些孤立顶点的组合情况。 利用图的伴随多项式是分析色等价性的关键工具。伴随多项式是图论中的一个重要概念，它与图的染色数密切相关。对于一个无向图G，其伴随多项式定义为A(G, x) = ∑(-1)^k(C_k * x^(n-k))，其中C_k是G的所有连通子图的数量，n是图G的顶点数。这个多项式在x取特定值时的零点与图的色数有关，特别是在x=1时，若A(G, 1) = 0，则表明图G至少需要3种颜色进行染色。 论文中，作者通过因式分解星图Sn+1的伴随多项式，揭示了这些图的结构特性，进而得到了它们的色等价图。这种方法揭示了不同组合图在染色性质上的相似性，即它们的最小染色数相同。 结论部分指出，通过研究图的补图（即删除所有边形成的图）的伴随多项式的因式分解，可以有效地推导出原图的色等价性。补图在很多情况下能提供关于原图性质的相反视角，因此这种方法为理解图的染色问题提供了新的思路。 这篇论文深入探讨了图的色等价性，特别是通过星图Sn+1的组合变体，使用了伴随多项式及其因式分解作为主要分析工具。这一研究对于理解和解决图的染色问题具有理论价值，并可能对图论领域内的其他问题研究产生启示。