图的三类染色及其概率方法
|
摘要
本文通过归纳定义了图的三类染色一无圈染色，邻点可区别的染色和点可区别的染色。应用Lovász局部引理的赋权形式，讨论并得到了任一最大度△≥4的图G，其邻点可区别的无圈边色数至多为16△~2。应用Lovász局部引理的一般形式，讨论并得到了任一最大度△≥32~2ln5，最小度δ≥32(△ln△)~(1/2)的图G，其邻点可区别的全色数至多为2△+1+2(△ln△)~(1/2)；进一步，若全色数χ_t(G)≤△+2，则其邻点可区别的全色数至多为△+2+2(△ln△)~(1/2)。然后，通过具体构造染色的方法讨论并给出了路、圈、完全图、星、扇、轮的Mycielski图，路与圈的联图P_m∨S_n的点可区别的全色数。
In this paper,by induction we define three kinds of colorings of graphs,which are acyclic coloring,adjacent vertex-distinguishing coloring and vertex-distinguishing coloring.With applying the weighted form of the Lovasz local lemma,we have discussed and obtained that the adjacent vertex distinguishing acyclic edge chromatic number is at most 16Δ~2 for any graph G with maximum degreeΔ≥4. With applying the general form of the Lovasz local lemma,we have discussed and obtained that the adjacent vertex distinguishing total chromatic number is at most 2Δ+1 + 2(ΔlnΔ)~(1/2) for any graph G with maximum degreeΔ≥32~2ln5 and minimum degreeδ≥32(ΔlnΔ)~(1/2);furthermore,the adjacent vertex distinguishing total chromatic number is at mostΔ+ 2 + 2(ΔlnΔ)~(1/2) if the total chromatic number X_t(G)≤Δ+ 2.Then with giving colorings of a graph, vertex distinguishing total chromatic numbers on Mycielski's graphs of path,cycle,complete graph,star,fan and wheel,and vertex distinguishing total chromatic numbers of P_m∨S_n are discussed and given,respectively.
In this paper,by induction we define three kinds of colorings of graphs,which are acyclic coloring,adjacent vertex-distinguishing coloring and vertex-distinguishing coloring.With applying the weighted form of the Lovasz local lemma,we have discussed and obtained that the adjacent vertex distinguishing acyclic edge chromatic number is at most 16Δ~2 for any graph G with maximum degreeΔ≥4. With applying the general form of the Lovasz local lemma,we have discussed and obtained that the adjacent vertex distinguishing total chromatic number is at most 2Δ+1 + 2(ΔlnΔ)~(1/2) for any graph G with maximum degreeΔ≥32~2ln5 and minimum degreeδ≥32(ΔlnΔ)~(1/2);furthermore,the adjacent vertex distinguishing total chromatic number is at mostΔ+ 2 + 2(ΔlnΔ)~(1/2) if the total chromatic number X_t(G)≤Δ+ 2.Then with giving colorings of a graph, vertex distinguishing total chromatic numbers on Mycielski's graphs of path,cycle,complete graph,star,fan and wheel,and vertex distinguishing total chromatic numbers of P_m∨S_n are discussed and given,respectively.
引文
[1] Bondy J A, Murty U S R. Graph Theory with Applications. London, Macmillan Press Ltd, 1976.
[2] Béla Bolloás. Modern Graph Theory. Springer, New York, Inc, 1998.
[3] Alon N., Spencer J. The Probabilistic Method. John Wiley & Sons, Inc, New York,1992.
[4] Michael Molloy, Bruce Reed. Graph Colouring and the Probabilistic Method. Springer, New York, Inc, 2002.
[5] Grünbaum B. Acyclic Coloring of Planar Graphs. Israel J. Math. 14, 1973(14):390～408.
[6] Alon N, Sadakov B and Zaks A. Acyclic Edge Colorings of Graphs. Journal of Graph Theory, 2001 (37): 157～167.
[7] Zhang Zhongfu, Liu Linzhong, Wang Jianfang. Adjacent Strong Edge Coloring of Graphs. Applied Mathematics Letters, 2002, 15(5): 623～626.
[8] Zhang Zhongfu etc. Adjacent Vertex-distinguishing Acyclic Edge Colorings of Graphs. Submitted.
[9] Zhang Zhongfu etc. On the Adjacent Vertex Distinguishing Total Coloring of Graphs. Science in China,Set. A,10(2004),1～8.
[10] S.Akbari,H. Bidkhori,and N.Nosrati. r-strong edge colorings of graphs, submitted.
[11] P.N.Balister,E.Gyori,J.Lehel,R.H.Schelp.Adjacent Vertex Distinguishing Edge Colorings. J.Graph theory, to appear.
[12] M.Ghandehari,H.Hatami. Two Upper Bounds for the Strong Edge Chromatic Number.preprint.
[13] H.Hatami.△ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number. J.Combin.Theory, Ser. B, 2005,1～11.
[14] Liu Xinsheng, Chen Xiang'en, Sun Yirong. An Upper Bound on the Adjacent Vertex-Distinguishing Total Chromatic Number of Graph, Discrete Mathematics. Submitted.
[15] Chang G J,Huang L,Zhu X. Circular Chromatic Number of Mycielski's Graphs. Discrete Mathematics. 1999,(205):23～37.
[16] Chen Xiang-en,Zhang Zhong-fu etc. Adjacent-Vertex-Distinguishing Total Chromatic Numbers on Mycielski's Graphs of Several kinds of Particular graphs. Journal of Lanzhou University(Natural Science),2005,41(2):117～122.
[17] Erdos 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.
[18] J. Beck, An Algorithmic Approach to the Lovász Local Lemma I, to appear in Random Structures and Algorithms.
[19] J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987.
[20] I. Algor and N. Alon, The star arboricity of graphs, Discrete Mathematics 75 (1989),11～22.
[21] 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.
[22] N. Alon and N. Linial, Cycles of length O modulo k in directed graphs, J. Combinatorial Theory, Set. B47(1989), 114～119.
[23] N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, to appear in Random Structures and Algorithms.
[24] S.Fiorini and R.J.Wilson. Edge Coloring of Graphs. Research Notes in Mathematics, Vol. 16,Pitamn,London(1977).
[25] P. Hansen, O. Marcotte. Graph Coloring and Application, AMS Providence, Rhode Island USA, 1999.
[26] H.Kronk and J.Mitchem. A Seven-Color theorem on the Sphere. Discrete mathematics, 5(1973):253～260.
[27] A.C.Burris. Vertex-Distinguishing Edge-Colorings. PhD thesis,Memphis State University, 1993.
[28] A.C.Burris and R.H.Schelp. Vertex-Distinguishing Proper Edge-Colorings. J.Graph Theory, 1997, 26(2): 73～82.
[29] P.N.Balister,O.M.Riordan,R.H.Schelp. Vertex Distinguishing Edge Colorings of Graphs . J.Graph Theory, 2003, 42(2): 95～109.
[30] C.Bazgan,A.Harkat-Benhamdine,Hao Li,M.Wozniak.On the Vertex-Distinguishing Proper Edge-Coloring of Graphs, J.Combin.Theory Ser.B 1999, 75(2): 288～301.
[31] P. N. Balister, B. Bollobás and R. H. Schelp. Vertex Distinguishing Colorings of Graphs with △(G)=2. Discrete Mathematics, 2002, 252: 17～29.
[32] O.Favaron,H.Li,and R.H.Schelp.Strong edge coloring of graphs. Discrete Math, 1996,159: 103～109.
[33] E.Dedo,D.Torri and Norma Zagaglia Salvi. The Observability of the Fibonacci and Lucas cubes. Discrete Mathematics, 255 (2002) :55～63.
[34] J.Cerny,M.Hornák,and R.Soták.Observability of a Graph.Math.Slovaca, 1996,46:21～31.
[35] M.Hornák,and R.Soták.Asymptotic behavior of the Observability of Q_n.Discrete Math, 1997,176: 139～148.
[36] M.Hornák,and R.Soták. Observability of Complete Multipartite Graphs with Equipotent Parts.Ars Combinatoria, 1995,41: 289～301.
[37] Liu J B, Li J W. On the Adjacent Strong Edge Chromatic Number of Maximal Outerplanar Graphs. Mathematics in Economics, 2001, 18(1): 43～45.
[38] Liu L Z, Jiao Y L, Zhang Z F, et al. On the Adjacent Strong Edge Coloring of Outerplanar Graph with △(G)≤3. Mathematics in Economics, 2001,18(2):68～71.
[39] 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.
[40] L. Z. Liu, Y.Z. Li, et al. On the Adjacent Strong Edge Coloring of Halin Graphs. J. Mathematical Research and Exposition, 2003,23(2):241～246.
[41] H.P.Yap. Total Coloring of Graphs. Lecture Notes in Mathematics 1623, Springer Verlag Berlin Heidelberg,1996.
[42] H.P.Yap etc. Total Chromatic Number of Graphs of High Degree.Ⅱ, J.Australian Math.Soc.,Ser.A, 53(1992): 219～228.
[43] A.V.Kostochka. The Total Coloring of a Multigraph with Maximal Degree 4. Discrete Math, 17(1977): 161～163.
[44] A.J.W.Hilton etc. The Relationship between Edge-Coloring Cojecture and A Total-Coloring Cojecture. J.Combin.Math.Combin.Comput, 10(1991): 83～95.
[45] H.R.Hind. An Upper Bound for the Total Chromatic Number. Graphs and Combinatorics, 6(1990): 153～159.
[46] Jensen T., Toft B. Graph Coloring Problems. Wiley, New York, 1995.
[47] G. Chartrand, L. Lesniak-Foster. Graph and Digraphs. Ind. Edition, Wadsworth Brooks/Cole, Monterey, CA, 1986.
[48] Reinhard Dietel. Graph Theory, Spring-Verlag New York, Inc, 1997.
[2] Béla Bolloás. Modern Graph Theory. Springer, New York, Inc, 1998.
[3] Alon N., Spencer J. The Probabilistic Method. John Wiley & Sons, Inc, New York,1992.
[4] Michael Molloy, Bruce Reed. Graph Colouring and the Probabilistic Method. Springer, New York, Inc, 2002.
[5] Grünbaum B. Acyclic Coloring of Planar Graphs. Israel J. Math. 14, 1973(14):390～408.
[6] Alon N, Sadakov B and Zaks A. Acyclic Edge Colorings of Graphs. Journal of Graph Theory, 2001 (37): 157～167.
[7] Zhang Zhongfu, Liu Linzhong, Wang Jianfang. Adjacent Strong Edge Coloring of Graphs. Applied Mathematics Letters, 2002, 15(5): 623～626.
[8] Zhang Zhongfu etc. Adjacent Vertex-distinguishing Acyclic Edge Colorings of Graphs. Submitted.
[9] Zhang Zhongfu etc. On the Adjacent Vertex Distinguishing Total Coloring of Graphs. Science in China,Set. A,10(2004),1～8.
[10] S.Akbari,H. Bidkhori,and N.Nosrati. r-strong edge colorings of graphs, submitted.
[11] P.N.Balister,E.Gyori,J.Lehel,R.H.Schelp.Adjacent Vertex Distinguishing Edge Colorings. J.Graph theory, to appear.
[12] M.Ghandehari,H.Hatami. Two Upper Bounds for the Strong Edge Chromatic Number.preprint.
[13] H.Hatami.△ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number. J.Combin.Theory, Ser. B, 2005,1～11.
[14] Liu Xinsheng, Chen Xiang'en, Sun Yirong. An Upper Bound on the Adjacent Vertex-Distinguishing Total Chromatic Number of Graph, Discrete Mathematics. Submitted.
[15] Chang G J,Huang L,Zhu X. Circular Chromatic Number of Mycielski's Graphs. Discrete Mathematics. 1999,(205):23～37.
[16] Chen Xiang-en,Zhang Zhong-fu etc. Adjacent-Vertex-Distinguishing Total Chromatic Numbers on Mycielski's Graphs of Several kinds of Particular graphs. Journal of Lanzhou University(Natural Science),2005,41(2):117～122.
[17] Erdos 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.
[18] J. Beck, An Algorithmic Approach to the Lovász Local Lemma I, to appear in Random Structures and Algorithms.
[19] J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987.
[20] I. Algor and N. Alon, The star arboricity of graphs, Discrete Mathematics 75 (1989),11～22.
[21] 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.
[22] N. Alon and N. Linial, Cycles of length O modulo k in directed graphs, J. Combinatorial Theory, Set. B47(1989), 114～119.
[23] N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, to appear in Random Structures and Algorithms.
[24] S.Fiorini and R.J.Wilson. Edge Coloring of Graphs. Research Notes in Mathematics, Vol. 16,Pitamn,London(1977).
[25] P. Hansen, O. Marcotte. Graph Coloring and Application, AMS Providence, Rhode Island USA, 1999.
[26] H.Kronk and J.Mitchem. A Seven-Color theorem on the Sphere. Discrete mathematics, 5(1973):253～260.
[27] A.C.Burris. Vertex-Distinguishing Edge-Colorings. PhD thesis,Memphis State University, 1993.
[28] A.C.Burris and R.H.Schelp. Vertex-Distinguishing Proper Edge-Colorings. J.Graph Theory, 1997, 26(2): 73～82.
[29] P.N.Balister,O.M.Riordan,R.H.Schelp. Vertex Distinguishing Edge Colorings of Graphs . J.Graph Theory, 2003, 42(2): 95～109.
[30] C.Bazgan,A.Harkat-Benhamdine,Hao Li,M.Wozniak.On the Vertex-Distinguishing Proper Edge-Coloring of Graphs, J.Combin.Theory Ser.B 1999, 75(2): 288～301.
[31] P. N. Balister, B. Bollobás and R. H. Schelp. Vertex Distinguishing Colorings of Graphs with △(G)=2. Discrete Mathematics, 2002, 252: 17～29.
[32] O.Favaron,H.Li,and R.H.Schelp.Strong edge coloring of graphs. Discrete Math, 1996,159: 103～109.
[33] E.Dedo,D.Torri and Norma Zagaglia Salvi. The Observability of the Fibonacci and Lucas cubes. Discrete Mathematics, 255 (2002) :55～63.
[34] J.Cerny,M.Hornák,and R.Soták.Observability of a Graph.Math.Slovaca, 1996,46:21～31.
[35] M.Hornák,and R.Soták.Asymptotic behavior of the Observability of Q_n.Discrete Math, 1997,176: 139～148.
[36] M.Hornák,and R.Soták. Observability of Complete Multipartite Graphs with Equipotent Parts.Ars Combinatoria, 1995,41: 289～301.
[37] Liu J B, Li J W. On the Adjacent Strong Edge Chromatic Number of Maximal Outerplanar Graphs. Mathematics in Economics, 2001, 18(1): 43～45.
[38] Liu L Z, Jiao Y L, Zhang Z F, et al. On the Adjacent Strong Edge Coloring of Outerplanar Graph with △(G)≤3. Mathematics in Economics, 2001,18(2):68～71.
[39] 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.
[40] L. Z. Liu, Y.Z. Li, et al. On the Adjacent Strong Edge Coloring of Halin Graphs. J. Mathematical Research and Exposition, 2003,23(2):241～246.
[41] H.P.Yap. Total Coloring of Graphs. Lecture Notes in Mathematics 1623, Springer Verlag Berlin Heidelberg,1996.
[42] H.P.Yap etc. Total Chromatic Number of Graphs of High Degree.Ⅱ, J.Australian Math.Soc.,Ser.A, 53(1992): 219～228.
[43] A.V.Kostochka. The Total Coloring of a Multigraph with Maximal Degree 4. Discrete Math, 17(1977): 161～163.
[44] A.J.W.Hilton etc. The Relationship between Edge-Coloring Cojecture and A Total-Coloring Cojecture. J.Combin.Math.Combin.Comput, 10(1991): 83～95.
[45] H.R.Hind. An Upper Bound for the Total Chromatic Number. Graphs and Combinatorics, 6(1990): 153～159.
[46] Jensen T., Toft B. Graph Coloring Problems. Wiley, New York, 1995.
[47] G. Chartrand, L. Lesniak-Foster. Graph and Digraphs. Ind. Edition, Wadsworth Brooks/Cole, Monterey, CA, 1986.
[48] Reinhard Dietel. Graph Theory, Spring-Verlag New York, Inc, 1997.