四川文理学院学报
四川文理學院學報
사천문이학원학보
SICHUAN UNIVERSITY OF ARTS AND SCIENCE JOURNAL
2012年
2期
17-20
,共4页
集染色%集色数%完全图%Halin图
集染色%集色數%完全圖%Halin圖
집염색%집색수%완전도%Halin도
set coloring%the set chromatic number%complete graph%Halin graph
对于非平凡连通图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成立.
對于非平凡連通圖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成立.
대우비평범련통도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성립.
For a non - trivial connected graph G, let c： V（G）---＋Nk be a vertex coloring of G where adjacent vertices may be col- ored the same. For a vertex v of G , the neighborhood color set cN（v） is the set of colors of the neighbors ofv. The coloring c is called a k set coloring if cN（u） #cN（v） for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number,x, （G） of G. It is proved that the set chromatic number of the Halin graph G（ Co, Tq ） with p 34 is 3, and that for any a Halin graph G（ Co, T ）, there exists p ＋ 1 q 〈2p - 2.
