Halin图的集染色

摘要：

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.

关键词：集染色、集色数、完全图、Halin图

所属期刊栏目：22

分类号：O157.5(代数、数论、组合理论)

资助基金：中央高校基本科研业务费专项基金2010LKSX06

在线出版日期：2012-06-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：17-20