安明強

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

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

安明強

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

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

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

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

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

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

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

由概率論知識可知

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

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

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

(1)正常點染色，

(2)每一條長為3的路上的點不是二色的.

為此，定義如下壞事件：

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

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

為了運用引理1，需進行以下幾個步驟：

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

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

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

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

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

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

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

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

(1)正常點染色，

(2)每一條長為3的路上的點不是二色的.

為此，定義如下指標變量：

(Ⅰ) 對每條邊uv，令

現(xiàn)只要證 Pr(X =0且 Y= 0)＞0 ，根據(jù)事實 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é)研究基金資助項目（20090222）

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