论局部标定图的色多项式及其应用  

On Chromatic Polynomials of Partial LabeledGraphs and Their Applications

作　　者：杜清晏[1,2] 李念祖 

机构地区：[1]内蒙古大学数学系 [2]上海第二工业大学应用数学系

出　　处：《内蒙古大学学报（自然科学版）》1998年第5期624-631,共8页Journal of Inner Mongolia University：Natural Science Edition

基　　金：国家自然科学基金

摘　　要：引入了局部标定图的概念，使得标定图和非标定图都成为它的两个特殊情形，它的色多项式统一了标定图的色多项式和非标定图的色多项式．研究了重迭于同一完全图上的局部标定图的色多项式的基本性质，揭示了局部标定图的色多项式与非标定图的色多项式之间的联系，进而，借助于局部标定图的色多项式给出了一个计算重迭于同一完全图的非标定图的色多项式的有效的计算程序．As a generalization of chromatic polynomials of labeled and unlabeled graphs,the notion of chromatic polynomials of partial labeled graphs is introduced.Partial labeled graphs which overlap on a labeled complete graph and their chromatic polynomials are considered.Some properties of them are obtained.On the basis of these results,an efficient method for calculating chromatic polynomials of some kinds of unlabeled graphs is presented.

关 键 词：色多项式 非标定图 局部标定图 

分 类 号：O157.5[理学—数学]