安明強(qiáng)

(天津科技大學(xué)理學(xué)院，天津 300457)

圖的星色數(shù)的兩個(gè)結(jié)果

安明強(qiáng)

(天津科技大學(xué)理學(xué)院，天津 300457)

圖G的星染色是圖G的正常點(diǎn)染色，使得圖G中沒有長(zhǎng)為3的路2-染色. 通過應(yīng)用概率方法中的非對(duì)稱局部引理，證明了任一最大度為Δ 的圖的星色數(shù)χs(G)≤ 48 Δ3. 通過應(yīng)用第一矩量原理和 Markov不等式，證明了對(duì)任一有n個(gè)頂點(diǎn)的最大度為 Δ 的圖G，其星色數(shù)χs(G )≤ n Δ .

點(diǎn)染色；正常染色；星染色；星色數(shù)；概率方法

1973年，Grünbaum[1]首先提出了星染色的概念，圖G的星染色是G的一個(gè)正常頂點(diǎn)染色滿足圖中無長(zhǎng)為 3的路是2?染色的.使得G有星染色的最小顏色數(shù)稱為G的星色數(shù)，記作χs(G).2004 年，F(xiàn)ertin 等在文獻(xiàn)[2]中得出樹、圈、完全二部圖、外平面圖等特殊圖的確切的星色數(shù). 2006年，劉信生等[3]提出了星邊染色的概念，若圖的一個(gè)正常邊染色滿足圖中沒有長(zhǎng)為 4的路是2?邊染色的，則稱此染色是圖的一個(gè)星邊染色，使得該圖有星邊染色的最小顏色數(shù)稱為星邊色數(shù)，記作χs′(G ).文獻(xiàn)[4–5]利用概率方法研究了鄰點(diǎn)可區(qū)別的邊染色和鄰點(diǎn)可區(qū)別的無圈邊染色，分別得到了其色數(shù)的上界χa′vd( G)≤ 300,χa′a( G)≤ 32Δ.這些方法對(duì)于本文的研究給予了一定的啟發(fā)，為本文的工作奠定了基礎(chǔ).

引理1[6](非對(duì)稱的局部引理)考慮事件的集合ε= { A1,A2,… ,An}，對(duì)每一個(gè) Ai，都存在Di(Di可以空)，使得每一個(gè) Ai與ε? (Di∪ Ai)互相獨(dú)立(對(duì)某個(gè)Di?ε)，如果對(duì)每個(gè)1≤i≤n，則ε中所有事件都不發(fā)生的概率是正的.

引理2[6](第一矩量原理)如果E(X)≤t，則Pr(X ≤t)＞0.

引理 2多用于X是正整數(shù)值且 E(X)＜ 1，則有Pr(X =0)＞0.

由概率論知識(shí)可知

本文通過運(yùn)用概率方法中的非對(duì)稱局部引理，以及第一矩量原理和 Markov不等式，分別得到星色數(shù)的兩個(gè)上界，其中后者得到的上界較小.文中未加述及的術(shù)語和符號(hào)可參見文獻(xiàn)[6–7].

定理1 對(duì)任一最大度為 Δ 的圖G, 有χs(G)≤48Δ3.

證明為了證明的方便，令 Δ=d,令 l= 48 d3,令C∶V(G ) → {1,2,… ,l}表示G的隨機(jī)正常(點(diǎn))染色，為了保證星染色，需滿足下面兩個(gè)條件：

(1)正常點(diǎn)染色，

(2)每一條長(zhǎng)為3的路上的點(diǎn)不是二色的.

為此，定義如下壞事件：

(Ⅰ) 對(duì)每一對(duì)相鄰的點(diǎn) u,v ∈V(G ),令 Au,v表示u和v被染成同種顏色的事件.

注意到如果(Ⅰ)與(Ⅱ)都不發(fā)生，則C是G的星染色.下面證明這兩類事件不發(fā)生的概率嚴(yán)格為正.

為了運(yùn)用引理1，需進(jìn)行以下幾個(gè)步驟：

(1)計(jì)算壞事件發(fā)生的概率：

(2)計(jì)算相關(guān)事件數(shù).

構(gòu)造相關(guān)圖H，H中的結(jié)點(diǎn)就是兩種類型的所有事件，其中兩個(gè)結(jié)點(diǎn)相鄰，當(dāng)且僅當(dāng) S1∩S2≠? .由于每個(gè)事件Xs1的發(fā)生僅依賴于S1中頂點(diǎn)所染的顏色，從而H就是這些事件的相關(guān)圖.由上述相關(guān)圖的構(gòu)造可得表1.

表1 相關(guān)圖H的構(gòu)造Tab.1 Construction of dependency graphH

(3)為了證明壞事件不發(fā)生的概率為正，只需以下兩點(diǎn)成立：

由(Ⅰ)、(Ⅱ)知，引理1適用，因此C是圖G的一個(gè) 48d3?星染色.從而定理1成立.

定理2 對(duì)任一有n個(gè)頂點(diǎn)的最大度為Δ的圖G,有χs(G )≤ nΔ.

證明為了證明的方便，可以令Δ=d,令l=nd,從顏色集合{1,2,…,l}中給圖G的每個(gè)頂點(diǎn)隨機(jī)均勻地分配一種顏色，使得每個(gè)這樣的選擇與所有其他的選擇互相獨(dú)立，為了保證星染色，必須使以下兩點(diǎn)成立：

(1)正常點(diǎn)染色，

(2)每一條長(zhǎng)為3的路上的點(diǎn)不是二色的.

為此，定義如下指標(biāo)變量：

(Ⅰ) 對(duì)每條邊uv，令

現(xiàn)只要證 Pr(X =0且 Y= 0)＞0 ，根據(jù)事實(shí) 1可得Pr(X = 0且 Y = 0)≥ 1 ? [P r(X ＞0 ) + Pr(Y ＞0)]＞0(令A(yù)1=

{ X = 0},A2= {Y = 0}，且A1={ X＞0},A2={Y ＞0 })，即只需證 Pr(X ＞0 ) +Pr(Y ＞0 )＜ 1即可.根據(jù) Markov不等式：P r(X ＞0 )≤ E(X ),所以只需證 E(X ) + E(Y )＜1即可.

［1］Grünbaum B. Acyclic colorings of planar graphs[J].Israel Journal of Mathematics，1973，14(4)：390–408.

［2］Fertin G，Raspaud A，Reed B. Star coloring of graphs[J].Journal of Graph Theory，2004，47(3)：163–182.

［3］Liu X S，Chen X E，Ou L F. A lower bound on cochromatic number for line graphs of a kind of graphs[J]. Applied Mathematics：A Journal of Chinese Universities，2006，21(3)：357–360.

［4］Hatami H. Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]. Journal of Combinatorial Theory：Series B，2005，95(2)：246–256.

［5］Liu X S，An M Q，Gao Y. An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph[J]. Acta Mathematicae Applicatae Sinica：English Series，2009，25(1)：137–140.

［6］Molloy Mi，Reed B. Graph Coloring and the Probabilistic Method[M]. New York：Springer，2002.

［7］Bondy J A，Murty U S R. Graph Theory with Applications[M]. London：Macmillan Press Ltd，1976.

Two Results of the Star Chromatic Number of Graphs

AN Ming-qiang
(College of Science，Tianjin University of Science & Technology，Tianjin 300457，China)

A star coloring of a graph G is a proper coloring of G such that no path of length 3 in G is bicolored. It was proved that every graph with maximum degree Δ has a star coloring with at most348Δ colors by using the Asymmetric Local Lemma of probabilistic method. And It was also proved that every graph with n vertices and with maximum degree Δ has a star coloring with at most nΔ colors by using the First Moment Principle and Markov’s Inequality.

vertex coloring；proper coloring；star coloring；star chromatic number；probabilistic method

O157.5

A

1672-6510(2010)05-0076-03

2010-03-01；

2010-05-18

天津科技大學(xué)科學(xué)研究基金資助項(xiàng)目（20090222）

安明強(qiáng)（1982—），男，甘肅天水人，講師，anmq@tust.edu.cn.