概率方法与图的染色问题
摘要
本文共分四个部分。
第一部分主要是引入一些在本文中经常出现的的基本概念和主要性质，并对某些概念给出具体实例。
第二部分介绍了第一矩量原理，Markov不等式以及四种形式的Lov(?)sz局部引理的内容，给出了这几种概率方法在超图上的应用，用几种思路找到了超图存在2-可染色的不同条件，其中着重对一般形式的Lov(?)sz局部引理给出应用实例，即无圈边染色，证明了当图G的围长大于等于700ΔlogΔ时，图G的无圈边色教小于等于△+2然后，用概率论的方法证明了几种形式的Lov(?)sz局部引理，并从中发现几种Lov(?)sz局部引理之间的关系，找出其不同的适用范围。
第三部分主要讨论了邻点可区别的边染色这一概念，用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的边色数。
第四部分引入了邻点可区别的全染色这一新的概念，并用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的全色数。
There are four parts in this paper.
In the first part, we introduce some fundamental concepts and main properties that often used in the paper. Some examples which are directed towards some concepts are given.
In the second part, we introduce the First Moment Principle. Markov's Inequality and four kinds of Lovasz Local Lemma, and give different applications in hypergraphs with these probabilistic methods, we find different conditions for a hypergraph to be 2-colorable with some kinds of thinkings. Among them the applications with the general Local Lemma arc the most important, such as acyclic edge colorings of graphs. We prove that the acyclic edge chromatic number of G is less than or equal to A + 2 for any graph G whose girth is at least 700△log△. We prove four kinds of Lovasz Local Lemma with the method of probability theory and discuss the relationship among them and their different applicable ranges.
In the third part, we discuss ''adjacent-vertex distinguishing edge colorings". We obtain the adjacent-vertex distinguishing edge chromatic numbers with the First Moment Principle. Markov's Inequality and some kinds of Lovasz Local Lemma, respectively.
In the last part, we discuss a new concept "adjacent-vertex distinguishing total colorings". We obtain the adjacent-vertex distinguishing total chromatic numbers with the First Moment Principle, Markov's Inequality and some kinds of Lovasz Local Lemma, respectively.
第一部分主要是引入一些在本文中经常出现的的基本概念和主要性质，并对某些概念给出具体实例。
第二部分介绍了第一矩量原理，Markov不等式以及四种形式的Lov(?)sz局部引理的内容，给出了这几种概率方法在超图上的应用，用几种思路找到了超图存在2-可染色的不同条件，其中着重对一般形式的Lov(?)sz局部引理给出应用实例，即无圈边染色，证明了当图G的围长大于等于700ΔlogΔ时，图G的无圈边色教小于等于△+2然后，用概率论的方法证明了几种形式的Lov(?)sz局部引理，并从中发现几种Lov(?)sz局部引理之间的关系，找出其不同的适用范围。
第三部分主要讨论了邻点可区别的边染色这一概念，用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的边色数。
第四部分引入了邻点可区别的全染色这一新的概念，并用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的全色数。
There are four parts in this paper.
In the first part, we introduce some fundamental concepts and main properties that often used in the paper. Some examples which are directed towards some concepts are given.
In the second part, we introduce the First Moment Principle. Markov's Inequality and four kinds of Lovasz Local Lemma, and give different applications in hypergraphs with these probabilistic methods, we find different conditions for a hypergraph to be 2-colorable with some kinds of thinkings. Among them the applications with the general Local Lemma arc the most important, such as acyclic edge colorings of graphs. We prove that the acyclic edge chromatic number of G is less than or equal to A + 2 for any graph G whose girth is at least 700△log△. We prove four kinds of Lovasz Local Lemma with the method of probability theory and discuss the relationship among them and their different applicable ranges.
In the third part, we discuss ''adjacent-vertex distinguishing edge colorings". We obtain the adjacent-vertex distinguishing edge chromatic numbers with the First Moment Principle. Markov's Inequality and some kinds of Lovasz Local Lemma, respectively.
In the last part, we discuss a new concept "adjacent-vertex distinguishing total colorings". We obtain the adjacent-vertex distinguishing total chromatic numbers with the First Moment Principle, Markov's Inequality and some kinds of Lovasz Local Lemma, respectively.
引文
[1] Alon N., Spencer J. The Probabilistic Method. John Wiley & Sons, Inc, New York,1992
[2] 谷超豪，数学词典，上海辞书出版社，1992
[3] Bondy J A, Murty U S R. Graph Theory with Applications. London. Macmillan Pross Ltd, 1976
[4] B(?)la Bollo(?)s. Modern Graph Theory. Springer, New York, Inc, 1998
[5] Zhang Zhongfu, Liu Linzhong, Wang Jianfang. Adjacent Strong Edge Coloring of Graphs. Applied Mathematics Letters. 2002, 15(5): 623～626
[6] Zhongfu Zhang, et al. On the Adjacent Vertex Distinguishing Total Coloring of Graphs. Technologic Report of Northwest Normal University, 2003. 118
[7] Michael Molloy, Bruce Reed. Graph Colouring and the Probabilistic Method. Springer,New York, Inc, 2002
[8] Erd(?)s P. Lov(?)sz L. (1975) Problems and Results on, 3-Chromatic Hypergraphs and Some Related Questions. In: " Infinite and Finite Sets " (A. Hajnal et al. Eds), Colloq. Math. Soc. J. Bolyai 11, North Holland, Amsterdam, 609～627
[9] Shearer J. On a Problem of Spencer. Combinatorica, 1985, 3:241～245
[10] J. Beck. An Algorithmic Approach to the Lov(?)sz Local Lemma I, to appear in Random Structures and Algorithms
[11] J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987.
[12] I. Algor and N. Alon, The star arboricity of graphs, Discrete Mathematics 75 (1989),11～22.
[13] N. Alon, A. Bar-Noy, N. Linial and D. Peleg, On the complexity of radio communication, Proc. 21th ACM STOC, Seattle, Washington, ACM Press (1989), 274～285.
[14] N. Alon, The linear arboricity of graphs, Israel J. Math. 62(1988), 311～325.
[15] N. Alon, The strong chromatic number of a graph, to appear in Random Structures and Algorithms.
[16] N. Alon and N. Linial,Cycles of length O modulo k in directed graphs, J. Combinatorial Theory, Ser. B 47(1989), 114～119.
[17] N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, to appear in Random Structures and Algorithms.
[18] N.. Alon, C. McDiarmid and B. Reed, Star Arboricity, to appear in Combinatorica.
[19] Sun Yirong, Yan Jingzhi. Relationship Between Girth and Acyclic Edge Chromatic Number of Graph.数学研究，2003. 2(36):136～139
[20] Alon N, Sadakov B and Zaks A. Acyclic Edge Colorings of Graphs. Journal of Graph Theory, 2001 (37): 157～167
[21] Burris A C and Schelp R H. Vertez-Distinguishing Proper Edge-Colorings. J of Graph Theory, 1997, 21:73～82
[22] P. N. Balister, B. Bollob(?)s and R.H. Schelp. Vertez Distinguishing Colorings of Graphs with △(G)=2. Discrete Mathematics, 2002, 252:170～29
[23] Liu J B, Li J W. On the Adjacent Strong Edge Chromatic Number of Maximal Outerplanar Graphs. Mathetmatics in Economics, 2001, 18(1): 43～45
[24] Liu L Z. Jiao Y L. Zhang Z F. et al. On. the Adjacent Strong Edgc Coloring of Outerplanar Graph with △(G)≤3. Mathematies in Economics, 2001.18(2):68～71
[25] D. S. Ma, L. Z. Liu and Z . F. Zhang. On the Adjacent Strong Edge Coloring of 1-Tree, J. Mathematical Research and Exposition, 2000, 20(2):299～305
[26] L. Z. Liu, Y.Z. Li, et al. On the Adjacent Strong Edge Coloring of Halin Graphs. J. Matttematical Research and Exposition, 2003.23(2):241～246
[27] G. Chartrand, L. Lesniak-Foster. Graph and Digraphs. Ind. Edition, Wadsworth Brooks/Cole, Monterey, CA, 1986
[28] Reinhard Dietel. Graph Theory, Spring-Verlag New York, Inc, 1997
[29] P. Hansen, O. Marcotte. Graph Coloring and Application, AMS Providence, Rhode Island USA, 1999
[30] Zhang Zhongfu etc. On the Adjacent Vertex-Distinguishin9 Total Coloring of P_n~k. Submitted
[31] Liu Xinsheng, Chen Xiang'en, Sun Yirong. A Upper Bound on the Adjacent Vertex-Distinguishing Total Chromatic Number of Graph, Discrete Mathematics. Submitted
[2] 谷超豪，数学词典，上海辞书出版社，1992
[3] Bondy J A, Murty U S R. Graph Theory with Applications. London. Macmillan Pross Ltd, 1976
[4] B(?)la Bollo(?)s. Modern Graph Theory. Springer, New York, Inc, 1998
[5] Zhang Zhongfu, Liu Linzhong, Wang Jianfang. Adjacent Strong Edge Coloring of Graphs. Applied Mathematics Letters. 2002, 15(5): 623～626
[6] Zhongfu Zhang, et al. On the Adjacent Vertex Distinguishing Total Coloring of Graphs. Technologic Report of Northwest Normal University, 2003. 118
[7] Michael Molloy, Bruce Reed. Graph Colouring and the Probabilistic Method. Springer,New York, Inc, 2002
[8] Erd(?)s P. Lov(?)sz L. (1975) Problems and Results on, 3-Chromatic Hypergraphs and Some Related Questions. In: " Infinite and Finite Sets " (A. Hajnal et al. Eds), Colloq. Math. Soc. J. Bolyai 11, North Holland, Amsterdam, 609～627
[9] Shearer J. On a Problem of Spencer. Combinatorica, 1985, 3:241～245
[10] J. Beck. An Algorithmic Approach to the Lov(?)sz Local Lemma I, to appear in Random Structures and Algorithms
[11] J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987.
[12] I. Algor and N. Alon, The star arboricity of graphs, Discrete Mathematics 75 (1989),11～22.
[13] N. Alon, A. Bar-Noy, N. Linial and D. Peleg, On the complexity of radio communication, Proc. 21th ACM STOC, Seattle, Washington, ACM Press (1989), 274～285.
[14] N. Alon, The linear arboricity of graphs, Israel J. Math. 62(1988), 311～325.
[15] N. Alon, The strong chromatic number of a graph, to appear in Random Structures and Algorithms.
[16] N. Alon and N. Linial,Cycles of length O modulo k in directed graphs, J. Combinatorial Theory, Ser. B 47(1989), 114～119.
[17] N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, to appear in Random Structures and Algorithms.
[18] N.. Alon, C. McDiarmid and B. Reed, Star Arboricity, to appear in Combinatorica.
[19] Sun Yirong, Yan Jingzhi. Relationship Between Girth and Acyclic Edge Chromatic Number of Graph.数学研究，2003. 2(36):136～139
[20] Alon N, Sadakov B and Zaks A. Acyclic Edge Colorings of Graphs. Journal of Graph Theory, 2001 (37): 157～167
[21] Burris A C and Schelp R H. Vertez-Distinguishing Proper Edge-Colorings. J of Graph Theory, 1997, 21:73～82
[22] P. N. Balister, B. Bollob(?)s and R.H. Schelp. Vertez Distinguishing Colorings of Graphs with △(G)=2. Discrete Mathematics, 2002, 252:170～29
[23] Liu J B, Li J W. On the Adjacent Strong Edge Chromatic Number of Maximal Outerplanar Graphs. Mathetmatics in Economics, 2001, 18(1): 43～45
[24] Liu L Z. Jiao Y L. Zhang Z F. et al. On. the Adjacent Strong Edgc Coloring of Outerplanar Graph with △(G)≤3. Mathematies in Economics, 2001.18(2):68～71
[25] D. S. Ma, L. Z. Liu and Z . F. Zhang. On the Adjacent Strong Edge Coloring of 1-Tree, J. Mathematical Research and Exposition, 2000, 20(2):299～305
[26] L. Z. Liu, Y.Z. Li, et al. On the Adjacent Strong Edge Coloring of Halin Graphs. J. Matttematical Research and Exposition, 2003.23(2):241～246
[27] G. Chartrand, L. Lesniak-Foster. Graph and Digraphs. Ind. Edition, Wadsworth Brooks/Cole, Monterey, CA, 1986
[28] Reinhard Dietel. Graph Theory, Spring-Verlag New York, Inc, 1997
[29] P. Hansen, O. Marcotte. Graph Coloring and Application, AMS Providence, Rhode Island USA, 1999
[30] Zhang Zhongfu etc. On the Adjacent Vertex-Distinguishin9 Total Coloring of P_n~k. Submitted
[31] Liu Xinsheng, Chen Xiang'en, Sun Yirong. A Upper Bound on the Adjacent Vertex-Distinguishing Total Chromatic Number of Graph, Discrete Mathematics. Submitted