图的星色数的两个结果

安明强

(天津科技大学理学院，天津 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.