图的1-非正常着色多项式OA
On 1-Improper Chromatic Polynomial of Graph
首先,运用G的边收缩图的色多项式建立P1(G,x)的一个递推公式,并由此给出了完全图、圈和树的1-非正常着色多项式的解析表达式.其次,给出了 Pd(G,x)的容斥公式.最后,将 Whitney 的破圈定理推广到 P1(G,x),并由此确定了它的前 4 项系数.结果表明:1-非正常着色多项式的系数一般而言既不是正负交替,也不是单峰的.
Firstly,a recursive formula for P1(G,x)is established by using the chromatic polynomials of the edge-contraction graphs of G,by which the explicit expressions of the 1-improper chromatic polynomial for complete graphs,cycles and trees are given.Secondly,the inclusion-exclusion formula of Pd(G,x)is given.Finally,Whitney's broken cycle theorem is generalized to P1(G,x),by which the first four coefficients of P1(G,x)are thereby determined.The result shows that the coefficients of the 1-improper chromatic polynom-i al are neither alternative in sign nor unimodal in general.
赵佳丽;钱建国
青海民族大学 数学与统计学院,青海 西宁 810007青海民族大学 数学与统计学院,青海 西宁 810007||厦门大学 数学科学学院,福建 厦门 361005
数理科学
色多项式非正常着色多项式对消结构容斥原理
chromatic polynomialimproper chromatic polynomialcancellation structureinclusion-exclusion principle
《华侨大学学报（自然科学版）》 2026 (3)
373-378,6
国家自然科学基金资助项目(12361070)青海民族大学研究生创新项目(07M2024009)
评论