关于图的均匀全染色
|
摘要
对图G的k-全染色法f，如果(?)i，j∈{1，2，…，k)，有||T_i|-|T_j||≤1，则称f为G的一个k-均匀全染色法，简记作G的k-ETC法。而称为G的均匀全色数。其中T_i=V_i∪E_i，(?)x∈T_i，f(x)=i。
本文研究了简单图的均匀全染色，给出了χ_(et)(G)=Δ(G)+1的一个充分条件和图在一定条件下均匀全色数的一个上界，结果如下：
定理1对于简单图G，若Δ(G)=|V(G)|-1，且|V(G)|≡1(mod 2)，则
定理2对于简单图G，若Δ(G)≤|V(G)|-2，则χ_(et)(G)≤|V(G)|。
由以上定理可推出一系列满足特殊条件的联图或多重联图的均匀全色数(见第三章)。在第四章中我们得到了P_m∨S_n、P_m∨F_n、P_m∨W_n、C_m∨S_n、C_m∨F_n和C_m∨W_n在m，n不同取值情况下的均匀全色数(见定理4至定理9)。在第五章中我们给出了星、扇和轮的Double图的均匀全色数(见定理10至定理12)。最后在所研究的基础上给出了关于图的均匀全染色问题的两个新的猜想：
猜想若图G仅有一个最大度点，则χ_(et)(G)=Δ(G)+1。
猜想若图G的最大度点互不相邻，则χ_(et)(G)=Δ(G)+1。
A total-coloring is said to be equitable if‖T_i|－|T_j‖≤1, where|T_i| is the elements (vertices and edges) number of the color ith. The minimum number of colors required for an equitable total-coloring of a simple graph G is denoted by x_(et)(G).
We study equitable total-coloring of simple graphs and obtain one sufficient condition for x_(et)(G)=△(G)＋1 and an upper bound of x_(et)(G) under some conditions:
Theorem 1 Let G be a simple graph. If△(G)=|V(G)|－1 and|V(G)|≡1(mod2), then x_(et)(G)=△(G)＋1.
Theorem 2 Let G be a simple graph. If△(G)≤|V(G)|－2, thenx_(et)(G)≤|V(G)|.
According to these theorems, we obtain the equitable total chromatic number of (multi) Join-graphs satisfying some conditions (to see Chapter 3). In Chapter 4 we obtain the equitable total chromatic numbers of P_m∨S_n, P_m∨F_n,P_m∨W_n,C_m∨S_n,C_m∨F_n and C_m∨W_n for all m,n(to see from Theorem 4 to Theorem 9). In Chapter 5 we derive the equitable total chromatic numbers of Double graphs of Star, Fan and Wheel (to see from Theorem 10 to Theorem 12). Finally, we propose two conjectures on Equitable Total-Coloring.
Conjecture 1 Let G be a simple graph. If G only has a vertex with maximum degree, then x_(et)(G)=△(G)＋1.
Conjecture 2 Let G be a simple graph. If G's vertexes with maximum degree are not adjacent, then x_(et)(G)=△(G)＋1.
本文研究了简单图的均匀全染色，给出了χ_(et)(G)=Δ(G)+1的一个充分条件和图在一定条件下均匀全色数的一个上界，结果如下：
定理1对于简单图G，若Δ(G)=|V(G)|-1，且|V(G)|≡1(mod 2)，则
定理2对于简单图G，若Δ(G)≤|V(G)|-2，则χ_(et)(G)≤|V(G)|。
由以上定理可推出一系列满足特殊条件的联图或多重联图的均匀全色数(见第三章)。在第四章中我们得到了P_m∨S_n、P_m∨F_n、P_m∨W_n、C_m∨S_n、C_m∨F_n和C_m∨W_n在m，n不同取值情况下的均匀全色数(见定理4至定理9)。在第五章中我们给出了星、扇和轮的Double图的均匀全色数(见定理10至定理12)。最后在所研究的基础上给出了关于图的均匀全染色问题的两个新的猜想：
猜想若图G仅有一个最大度点，则χ_(et)(G)=Δ(G)+1。
猜想若图G的最大度点互不相邻，则χ_(et)(G)=Δ(G)+1。
A total-coloring is said to be equitable if‖T_i|－|T_j‖≤1, where|T_i| is the elements (vertices and edges) number of the color ith. The minimum number of colors required for an equitable total-coloring of a simple graph G is denoted by x_(et)(G).
We study equitable total-coloring of simple graphs and obtain one sufficient condition for x_(et)(G)=△(G)＋1 and an upper bound of x_(et)(G) under some conditions:
Theorem 1 Let G be a simple graph. If△(G)=|V(G)|－1 and|V(G)|≡1(mod2), then x_(et)(G)=△(G)＋1.
Theorem 2 Let G be a simple graph. If△(G)≤|V(G)|－2, thenx_(et)(G)≤|V(G)|.
According to these theorems, we obtain the equitable total chromatic number of (multi) Join-graphs satisfying some conditions (to see Chapter 3). In Chapter 4 we obtain the equitable total chromatic numbers of P_m∨S_n, P_m∨F_n,P_m∨W_n,C_m∨S_n,C_m∨F_n and C_m∨W_n for all m,n(to see from Theorem 4 to Theorem 9). In Chapter 5 we derive the equitable total chromatic numbers of Double graphs of Star, Fan and Wheel (to see from Theorem 10 to Theorem 12). Finally, we propose two conjectures on Equitable Total-Coloring.
Conjecture 1 Let G be a simple graph. If G only has a vertex with maximum degree, then x_(et)(G)=△(G)＋1.
Conjecture 2 Let G be a simple graph. If G's vertexes with maximum degree are not adjacent, then x_(et)(G)=△(G)＋1.
引文
[1] J A Bondy, U S R Murty. Graph Theory with Applications [M]. The Macmillan Press LTD, 1976.
[2] N Robertson, D Sanders, P Seymour and R Thomas. The Four-color Theorem [J]. Journal of Combin Theory Ser B, 1997, 70:2-44.
[3] T R Jensen and B Toft. Graph Coloring Problems [M]. John Wiley & Sons, Inc. 1995, New York.
[4] F S Roberts. New Directions in Graph Theory (with an emphasis on the role of application) [J]. Annals of Discrete Math, 55 (1993):13-44.
[5] F S Roberts, From Garbage to Rainbows: Generalizations of Graph Coloring and their Applications in Graph Theory, Combinatorics and Applications, Vol.2. Y. Alavi. G Chartrand, O R Oellermanu and A J Schwenk (editory). Wiley. New York, 1031-1052 (1991).
[6] H P Yap. Total Colorings of Graphs [M]. Berlin: Lecture Notes in Mathematics, 1623, Springer, 1996.
[7] 张忠辅，王建方．关于图的全着色-一个综述[J]．数学进展，4(1992)，390-397．
[8] C Bazgan, A Harkat-Benhamdine, H Li, ed al. On the vertex-distinguishing proper edge-colo-rings of graphs [J]. Journal of Combin Theory Ser B, 1999, 75(2):288-301.
[9] A C Burris, R H Schelp. Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory, 1997, 26(2):73-82.
[10] 张忠辅，李敬文，陈祥恩，等．图的距离不大于β的任意两点可区别的边染色[J]．数学学报，2006，49(3)：703-708．
[11] 马刚，马少仙，张忠辅．图P_m∨W_n的点可区别边色数[J]．兰州大学学报，2007，43(2)：103-106．
[12] 张忠辅，李敬文，陈祥恩 等．图的距离不大于β的点可区别的全染色[J]．中国科学，A辑，2006，36(10)：1119-1130．
[13] 马少仙，李敬文，田双亮等．S_(m，n)图的强边色数及点可区别全色数[J]．西北民族大学学报，2005，26(2)：18-20．
[14] Zhang Zhongfu, Liu Lingzhong, Wang Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002,15: 623～626.
[15] 马刚，马明，张忠辅．皇冠图G_(n，m)的邻点可区别边色数[J]．华东交通大学学报，2005，22(2)：141-143．
[16] 张忠辅，陈祥恩，李敬文 等．关于图的邻点可区别全染色[J]．中国科学，A辑，2004，34(5)：574～583．
[17] 马刚，张忠辅．圈与星联图的邻点可区别全染色[J]．苏州科技学院学报，2006，23(1)：13-15．
[18] A J W Hilton, D de Werra. A Sufficient Condition for Equitable Edge-colouring of Simple Graphs [J]. Discrete Mathematics, 1994, 128:179-201.
[19] H L Fu. Some results on equalized total coloring [J]. Congressus Numerantium, 1994, 102: 111-119.
[20] Wang Weifan. Equitable total coloring of graphs with maximum degree 3[J]. Graphs and Combinatorics, 2002, 18:677-685.
[21] 张忠辅．关于图的均匀全染色[R]．天津：南开大学数学研究所，组合数学与图论，1996．
[22] W Meyer. Equitable coloring [J]. American Mathematics Monthly, 1973, 80:920-922.
[23] V G Vizing. On an estimate of the chromatic class of a p-graph[J], (Russian). Diskret. Analiz, 1964, 3:25-30.
[24] 刘永平．一些特殊图类的笛卡尔积和倍图的邻点可区别的全染色[D]．兰州，兰州大学：2006．
[25] 王海英，孙良．两类图的Mycielski图的均匀全色数[J]．科技导报，2005，23(8)：29-30．
[26] 李琼，卜月华．两类Mycielski图及一些平面图的均匀全色数[J]．数学研究，2006，39(4)：401-409．
[27] 张忠辅，张建勋．第Ⅰ类图的若干充分条件[J]．数学杂志，1985，5(2)：161-165．
[28] Zhang Zhongfu, Wang Wei-fan, Bau Sheng, et al. On the Equitable Total Colorings of Some Join Graphs[J]. Journal of Information & Computational Science, 2005, 2(4): 829-834.
[29] 朱俊蕾，卜月华．图P_n∨K(m，n)的均匀全色数[J]．浙江师范大学学报，2007，1：64-70．
[30] 马刚，马少仙，张忠辅．关于W_m∨S_n的均匀全染色[J]．数学研究，2007，40(3)：338-342．
[31] 刘林忠，李敬文，张忠辅．若干平面图的均匀全染色[J]．兰州铁道学院学报，1996，15(4)：85-91．
[32] 栗永安．若干图的均匀全染色[J]．兰州铁道学院学报，1997，16(3)：79-82．
[2] N Robertson, D Sanders, P Seymour and R Thomas. The Four-color Theorem [J]. Journal of Combin Theory Ser B, 1997, 70:2-44.
[3] T R Jensen and B Toft. Graph Coloring Problems [M]. John Wiley & Sons, Inc. 1995, New York.
[4] F S Roberts. New Directions in Graph Theory (with an emphasis on the role of application) [J]. Annals of Discrete Math, 55 (1993):13-44.
[5] F S Roberts, From Garbage to Rainbows: Generalizations of Graph Coloring and their Applications in Graph Theory, Combinatorics and Applications, Vol.2. Y. Alavi. G Chartrand, O R Oellermanu and A J Schwenk (editory). Wiley. New York, 1031-1052 (1991).
[6] H P Yap. Total Colorings of Graphs [M]. Berlin: Lecture Notes in Mathematics, 1623, Springer, 1996.
[7] 张忠辅，王建方．关于图的全着色-一个综述[J]．数学进展，4(1992)，390-397．
[8] C Bazgan, A Harkat-Benhamdine, H Li, ed al. On the vertex-distinguishing proper edge-colo-rings of graphs [J]. Journal of Combin Theory Ser B, 1999, 75(2):288-301.
[9] A C Burris, R H Schelp. Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory, 1997, 26(2):73-82.
[10] 张忠辅，李敬文，陈祥恩，等．图的距离不大于β的任意两点可区别的边染色[J]．数学学报，2006，49(3)：703-708．
[11] 马刚，马少仙，张忠辅．图P_m∨W_n的点可区别边色数[J]．兰州大学学报，2007，43(2)：103-106．
[12] 张忠辅，李敬文，陈祥恩 等．图的距离不大于β的点可区别的全染色[J]．中国科学，A辑，2006，36(10)：1119-1130．
[13] 马少仙，李敬文，田双亮等．S_(m，n)图的强边色数及点可区别全色数[J]．西北民族大学学报，2005，26(2)：18-20．
[14] Zhang Zhongfu, Liu Lingzhong, Wang Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002,15: 623～626.
[15] 马刚，马明，张忠辅．皇冠图G_(n，m)的邻点可区别边色数[J]．华东交通大学学报，2005，22(2)：141-143．
[16] 张忠辅，陈祥恩，李敬文 等．关于图的邻点可区别全染色[J]．中国科学，A辑，2004，34(5)：574～583．
[17] 马刚，张忠辅．圈与星联图的邻点可区别全染色[J]．苏州科技学院学报，2006，23(1)：13-15．
[18] A J W Hilton, D de Werra. A Sufficient Condition for Equitable Edge-colouring of Simple Graphs [J]. Discrete Mathematics, 1994, 128:179-201.
[19] H L Fu. Some results on equalized total coloring [J]. Congressus Numerantium, 1994, 102: 111-119.
[20] Wang Weifan. Equitable total coloring of graphs with maximum degree 3[J]. Graphs and Combinatorics, 2002, 18:677-685.
[21] 张忠辅．关于图的均匀全染色[R]．天津：南开大学数学研究所，组合数学与图论，1996．
[22] W Meyer. Equitable coloring [J]. American Mathematics Monthly, 1973, 80:920-922.
[23] V G Vizing. On an estimate of the chromatic class of a p-graph[J], (Russian). Diskret. Analiz, 1964, 3:25-30.
[24] 刘永平．一些特殊图类的笛卡尔积和倍图的邻点可区别的全染色[D]．兰州，兰州大学：2006．
[25] 王海英，孙良．两类图的Mycielski图的均匀全色数[J]．科技导报，2005，23(8)：29-30．
[26] 李琼，卜月华．两类Mycielski图及一些平面图的均匀全色数[J]．数学研究，2006，39(4)：401-409．
[27] 张忠辅，张建勋．第Ⅰ类图的若干充分条件[J]．数学杂志，1985，5(2)：161-165．
[28] Zhang Zhongfu, Wang Wei-fan, Bau Sheng, et al. On the Equitable Total Colorings of Some Join Graphs[J]. Journal of Information & Computational Science, 2005, 2(4): 829-834.
[29] 朱俊蕾，卜月华．图P_n∨K(m，n)的均匀全色数[J]．浙江师范大学学报，2007，1：64-70．
[30] 马刚，马少仙，张忠辅．关于W_m∨S_n的均匀全染色[J]．数学研究，2007，40(3)：338-342．
[31] 刘林忠，李敬文，张忠辅．若干平面图的均匀全染色[J]．兰州铁道学院学报，1996，15(4)：85-91．
[32] 栗永安．若干图的均匀全染色[J]．兰州铁道学院学报，1997，16(3)：79-82．