圖的星色數的兩個結果

安明強

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

圖的星色數的兩個結果

安明強

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

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

點染色；正常染色；星染色；星色數；概率方法

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

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

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

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

由概率論知識可知

本文通過運用概率方法中的非對稱局部引理，以及第一矩量原理和 Markov不等式，分別得到星色數的兩個上界，其中后者得到的上界較小.文中未加述及的術語和符號可參見文獻[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被染成同種顏色的事件.

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

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

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

(2)計算相關事件數.

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

表1 相關圖H的構造Tab.1 Construction of dependency graphH

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

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

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

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

(1)正常點染色，

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

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

(Ⅰ) 對每條邊uv，令

現只要證 Pr(X =0且 Y= 0)＞0 ，根據事實 1可得Pr(X = 0且 Y = 0)≥ 1 ? [P r(X ＞0 ) + Pr(Y ＞0)]＞0(令A1=

{ X = 0},A2= {Y = 0}，且A1={ X＞0},A2={Y ＞0 })，即只需證 Pr(X ＞0 ) +Pr(Y ＞0 )＜ 1即可.根據 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

天津科技大學科學研究基金資助項目（20090222）

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