若干图类的邻强边染色与2-强边染色问题研究
|
摘要
具有重要的理论意义和实际意义的各种染色问题,一直是图论中的热点话题之一。离散系统中的许多问题都可以转化为图着色问题,例如,给定图G,不包含子图的G的n个顶点的图的边的最大数目就依赖于图G的色数。因此Jensen和Toft断言:图着色理论在离散数学中处于中心的地位。在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规则进行分类的问题,例如时间表问题、排序问题、排课表问题、存储问题、电路安排、任务分配等等,都与图着色理论密切相关。
所谓图着色是指对图中的顶点、边(对平面图而言还有面)等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色。随着染色理论的发展又出现了许多新的染色,例如:全着色、列表着色、点强全着色、强边着色、强着色、关联着色、圈着色、距离面着色、区间着色、r-强边着色、完备着色及动态着色等,这些染色已成为现在图着色领域中新的热点.对于过去很多未解决的问题我们可以把它转化为一个新的染色问题,使原问题变得简单易懂并且便于研究。
本文主要研究的是图的邻强边染色与2-强边染色问题。首先借助于Akbari对树2-强边染色及3-强边染色的研究与张忠辅对树邻强边染色的研究,给出了对树进行2-强边染色时,2-强边色数等于最大度加1的充分条件是具有最大度的两个顶点的距离小于等于2。然后根据圈、完全图、完全二部图、轮图、项链、P_n~2、P_n~3、P_n~4、P_n~5、单圈图、若干联图、方形网格与六角网络的结构特点及其具有最大度的顶点之间的关系,研究了它们的2-强边染色问题,确定了它们的2-强边色数与最大度的关系,并且给出了它们的2-强边染色方案。
The coloring problems is one of popular problems in graph theory because of it's profound significance in both theory and practice.Many issues in discrete systems can be translated into the problems of graph coloring.For example,the edge maximum of n-order graph which don't contain a certain graph G as a subgraph depends on the chromatic number of the graph.Therefore T R.Jensen and B.Toft asserted:the graph coloring theory in discrete mathematics at the center position.In real life,many areas will be dealt with the object of a certain set of rules according to certain classification of the problem.For example,schedule,scheduling,time-table problem,the problem of storing,circuit arrangement,task allocation,and so on.These problems are closely related to coloring theory.
The so-called graph coloring is refers speaking of the graph in the vertex,edge(to the plane graph also has face) and so on the element carries on the classification according to the certain rule.Object dissimilarity or rule dissimilarity,then has all kinds of colotings.With the development of coloring theory,there are many new coloring, such as total coloring,list coloring,strong edge coloring,strong coloring,choosable coloring,r-strong edge color and so on hundred and thousand of colouring ways.These has bscome new hot spots in the graph colouring.As to the unresolved questions in the past,we can put them into a new coloring problem such that it is easy to understand and convenient to study.
In this paper,we discuss the adjacent strong edge coloring and 2-strong edge coloring of some graphs.First,with the research of 2-strong edge coloring and 3-strong edge coloring of tree from Akbari and adjacent strong edge coloring of tree from Zhang Zhongfu,a sufficient condition is proposed that 2-strong edge coloring number equals to the maximum degree plus one.Then according to the struct of cycle,complete graph, complete bipartite graph,wheel,nacklace,P_n~2,P_n~3,P_n~4,P_n~5,monocycle graph,some join-graphs,square mesh,hexagonal mesh and the relationship between the vertexes with the maximum degree,the 2-strong edge coloring of these graphs is studied to obtain the relationship of 2-strong edge coloring number and the maximum degree. Besides,the coloring method on the 2-strong edge coloring of these graphs are given.
所谓图着色是指对图中的顶点、边(对平面图而言还有面)等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色。随着染色理论的发展又出现了许多新的染色,例如:全着色、列表着色、点强全着色、强边着色、强着色、关联着色、圈着色、距离面着色、区间着色、r-强边着色、完备着色及动态着色等,这些染色已成为现在图着色领域中新的热点.对于过去很多未解决的问题我们可以把它转化为一个新的染色问题,使原问题变得简单易懂并且便于研究。
本文主要研究的是图的邻强边染色与2-强边染色问题。首先借助于Akbari对树2-强边染色及3-强边染色的研究与张忠辅对树邻强边染色的研究,给出了对树进行2-强边染色时,2-强边色数等于最大度加1的充分条件是具有最大度的两个顶点的距离小于等于2。然后根据圈、完全图、完全二部图、轮图、项链、P_n~2、P_n~3、P_n~4、P_n~5、单圈图、若干联图、方形网格与六角网络的结构特点及其具有最大度的顶点之间的关系,研究了它们的2-强边染色问题,确定了它们的2-强边色数与最大度的关系,并且给出了它们的2-强边染色方案。
The coloring problems is one of popular problems in graph theory because of it's profound significance in both theory and practice.Many issues in discrete systems can be translated into the problems of graph coloring.For example,the edge maximum of n-order graph which don't contain a certain graph G as a subgraph depends on the chromatic number of the graph.Therefore T R.Jensen and B.Toft asserted:the graph coloring theory in discrete mathematics at the center position.In real life,many areas will be dealt with the object of a certain set of rules according to certain classification of the problem.For example,schedule,scheduling,time-table problem,the problem of storing,circuit arrangement,task allocation,and so on.These problems are closely related to coloring theory.
The so-called graph coloring is refers speaking of the graph in the vertex,edge(to the plane graph also has face) and so on the element carries on the classification according to the certain rule.Object dissimilarity or rule dissimilarity,then has all kinds of colotings.With the development of coloring theory,there are many new coloring, such as total coloring,list coloring,strong edge coloring,strong coloring,choosable coloring,r-strong edge color and so on hundred and thousand of colouring ways.These has bscome new hot spots in the graph colouring.As to the unresolved questions in the past,we can put them into a new coloring problem such that it is easy to understand and convenient to study.
In this paper,we discuss the adjacent strong edge coloring and 2-strong edge coloring of some graphs.First,with the research of 2-strong edge coloring and 3-strong edge coloring of tree from Akbari and adjacent strong edge coloring of tree from Zhang Zhongfu,a sufficient condition is proposed that 2-strong edge coloring number equals to the maximum degree plus one.Then according to the struct of cycle,complete graph, complete bipartite graph,wheel,nacklace,P_n~2,P_n~3,P_n~4,P_n~5,monocycle graph,some join-graphs,square mesh,hexagonal mesh and the relationship between the vertexes with the maximum degree,the 2-strong edge coloring of these graphs is studied to obtain the relationship of 2-strong edge coloring number and the maximum degree. Besides,the coloring method on the 2-strong edge coloring of these graphs are given.
引文
[1]S.Akbari,H.Bidkhpri,N.Nosrati.r-Strong edge colorings of graphs.Discrete mathmatics,2006,306:3005-3010.
[2]R.J.Faudree,R.H.Schelp,Zs.Zuza.The strong chromatic index of graphs.Twelfth British Combinatorial Conference,Norwich 1989,Ars Combin.B,1900,29:205-211.
[3]Ofavaron,H.Li,R.n.Schelp.Strong edge colorings of graphs.Discrete mathmatics,1996,159:103-109.
[4]C.Bazgan,A.H.Harkat-Benhamdine,H.Li,M.Wozniak.On the vertex-distinguishing proper edge-colorings of graphs.J.Combin.Theory Ser,B,1999,75:288-301.
[5]A.Benkouar,Y.Manoussakis,R.Saad.The number of 2-edge-colored complete graphs with unique hamiltonian alternating cycle.Discrete Mathematics,2003,163:1-10.
[6]M.Maydanskiy.The incidence coloring conjecture for graphs of maximum degree 3.Discrete Mathematics,2005,292:131-141.
[7]X.Liu,Y.Li.The incidence chromatic number of some graphs.Int.J.Math.Math,Sci.2005,5:803-813.
[8]Z.Zhang,L.Liu,J.Wang.Adjacent strong edge coloring of graphs.Applied Mathematics Letters,2002,15:623-626.
[9]Daniel W.Cranston.Strong edge-coloring of graphs with maximum degree 4 using 22 colors.Discrete Mathematics,2006,306:2772-2778.
[10]Janka Rudasova,Roman Sotak.Vertex-distinguishing proper edge coloring of some regular graphs.Discrete Mathematics,2008,308:795-802.
[11]Cristina Bazgan,Amel narkat-Benhamdine,HaD Li.A note on the vertex-distinguishing proper coloring of graphs with large minimum degree.Discrete Mathematics,2001,236:37-42.
[12]田宝玉.Halin图的若干染色研究:(硕士学位论文).大连海事大学,2006.
[13]A.Kemnitz,M.Marangio.[r,s,t]-colorings of graphs.Discrete Mathematics,2007,307:199-207.
[14]Liu Linzhong,Li Yinzgen,Zhang Zhongfu.On the adjacent strong edge coloring of Halin graph.Journal of Mathematical Research & Exposition,2003,23(2):241-246.
[15] Liu Linzhong, Zhang Zhongfu, Wang jianfang . On the vertex strong total coloring for Halin graphs with △(G)≤5. Mathmatics In Economics, 2002, 19(1): 77-80.
[16] Weibin, Liu Linzhong, Zhang Zhongfu. On the Agjacent strong edge coloring for Halin graphs with △(G) = 4. Mathmatics In Economics, 2001, 18(4): 82-85.
[17] Andrzej Czygrinow, Brendan Nagle. Strong edge colorings of uniform graphs. Discrete Mathematics, 2004, 286: 291-223.
[18] A. Nadolski. The circular chromatic index of some class 2 graphs. Discrete Mathematics, 2007, 307: 1447-1454.
[19] Zhang Zhongfu, Liu Linzhong. On the complete chromatic number of Halin graph. Acata Math. Appl. Sinica, 1997, 13(1): 102-106.
[20] Zhang Zhongfu, Liu Linzhong , Wang jianfang. On the strong edge coloring of outer plane graphs. Journal of Mathematical Research & Exposition, 2005, 25(2): 255-266.
[21] M. Mollly, B. Reed. A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B, 1997, 69: 103-109.
[22] Liu Linzhong, Xie Jiguo and Zhang Zhongfu. On the vertex strong total coloring of graphs. Mathematics In Dconomics, 1998, 15(3): 52-55.
[23] Zhang Zhongfu, Zhang Jianxun, Wang Jianfang. The total chromatic number of some graphs. Sci.Sinica, Ser. A, 1988, 31(12): 1434-1441.
[24] P. N. Balister, B. Bollobas, R. H. Schelp. Vertex distinguishing colorings of graphs with △(G) = 2. Discrete Mathematics, 2002, 252: 17-29.
[25] C.N.Campos, C. p. de Mello. The total chromatic number of some bipartite graphs. Electronic Notes in Discrete Mathematics, 2005, 22: 557-561.
[26] P. N. Balister, E. Gyori, J.Lehel, R. H. Schelp, Adjacent vertex distinguishing Edge- Colorings. Discrete Mathematics, 2007, 21(1): 237-250.
[27] H.Wang. On the adjacent vertex distinguishing total chromatic numbers of graphs with △(G) = 3. J. Combin. Optim, 2007, 14: 87-109.
[28] Armen S. Asratiana, C. J. Casselgrenb. On interval edge colorings of (α,β)-biregular bipartite graphs. Discrete Mathematics, 2006, 307: 1951-1956.
[29] P.Wittmann. Vertex-distinguishing edge-colorings of 2- regular graphs. Discrete Mathematics, 1997, 79: 265-277.
[30]严谦泰,冉红.P_n~k的均匀全染色.大学数学,2007,23(3):59-64.
[31]张忠辅,强会英.关于C_n~4∨C_n~5(n≡0(mod5))的邻强边色数.兰州交通大学学报,2005,6(24):133-135.
[32]赵新梅,陈祥恩.单圈图的邻强边染色.兰州交通大学学报,2005,24(6):0138-0140.
[33]陈祥恩,张忠辅.P_m∨P_n的邻点可区别全染色.西北师范大学学报,2005,41(1):13-15.
[34]马明,刘华等.P_n∨P_m的邻点可区别边染色.经济数学,2005,22(2):215-219.
[35]包世堂,赵传成等.P_m∨K_n的点可区别边染色.甘肃高师学报,2004,9(5):16-17.
[36]晁福刚,强会英,闫丽宏.P_m∨S_n的邻点可区别全染色.经济数学,2005,22(3):327-330.
[37]陈克斌,李秦,等桂梅.星和完全等二部图联图的邻强边染色.石河子大学学报,2006,24(5):657-660.
[38]刘利群,陈祥恩.一类联图的点可区别正常边染色.西北师范大学学报(自然科学版),2006,42(5):21-25.
[39]马少仙,马刚,张忠辅.路与星联图的点可区别边染色.山东科技大学学报,2005,24(3):90-93.
[40]唐国梅,马刚,马少仙.关于P_m∨S_n的邻点可区别全染色.华东交通大学学报,2006,23(5):133-135.
[41]仇鹏翔,程耀东.关于P_n∨K_(n,n)的邻强边染色.兰州交通大学学报,2006,25(4):143-146.
[42]仇鹏翔,程耀东,田双亮.星和完全等二部图联图的点可区别均匀边染色.数学的实践与认识,2007,37(22):165-172.
[43]张忠辅,李敬文,赵传成等.若干联图的点可区别均匀边色数.数学学报,2007,50(1):197-204.
[44]马刚,刘华,唐国梅等.圈和扇的联图的全染色.华东交通大学学报,2005,4(22):152-154.
[45]田双亮.若干联图的邻点可区别全染色.西北民族大学学报,2006,1:0005-0007.
[46]王继顺,邱泽阳,张忠辅.联图的邻点可区别全染色.应用数学学报,2006,29(5):879-844.
[47]董海燕,孙磊.几类有趣图的邻点可区别全染色.山东科学,2006,19(2):9-10.
[48]王颜妮,王丽伟,刘萍.几类图的邻点可区别的全染色.科学技术与工程,2007,7(13):3048-3051.
[49]张忠辅,陈祥恩,李敬文等.关于图的邻点可区别全染色.中国科学A辑数学,2004,34(5):574-583.
[50]王朝瑞,图论.北京理工大学出版社,2000.
[51]卢开澄,图论及其应用.清华大学出版社,1981.
[52]陈子歧,朱必文,刘峙山.图论.高等教育出版社,1990.
[53]哈拉里F.图论[M].上海:上海科学技术出版社,1980.
[2]R.J.Faudree,R.H.Schelp,Zs.Zuza.The strong chromatic index of graphs.Twelfth British Combinatorial Conference,Norwich 1989,Ars Combin.B,1900,29:205-211.
[3]Ofavaron,H.Li,R.n.Schelp.Strong edge colorings of graphs.Discrete mathmatics,1996,159:103-109.
[4]C.Bazgan,A.H.Harkat-Benhamdine,H.Li,M.Wozniak.On the vertex-distinguishing proper edge-colorings of graphs.J.Combin.Theory Ser,B,1999,75:288-301.
[5]A.Benkouar,Y.Manoussakis,R.Saad.The number of 2-edge-colored complete graphs with unique hamiltonian alternating cycle.Discrete Mathematics,2003,163:1-10.
[6]M.Maydanskiy.The incidence coloring conjecture for graphs of maximum degree 3.Discrete Mathematics,2005,292:131-141.
[7]X.Liu,Y.Li.The incidence chromatic number of some graphs.Int.J.Math.Math,Sci.2005,5:803-813.
[8]Z.Zhang,L.Liu,J.Wang.Adjacent strong edge coloring of graphs.Applied Mathematics Letters,2002,15:623-626.
[9]Daniel W.Cranston.Strong edge-coloring of graphs with maximum degree 4 using 22 colors.Discrete Mathematics,2006,306:2772-2778.
[10]Janka Rudasova,Roman Sotak.Vertex-distinguishing proper edge coloring of some regular graphs.Discrete Mathematics,2008,308:795-802.
[11]Cristina Bazgan,Amel narkat-Benhamdine,HaD Li.A note on the vertex-distinguishing proper coloring of graphs with large minimum degree.Discrete Mathematics,2001,236:37-42.
[12]田宝玉.Halin图的若干染色研究:(硕士学位论文).大连海事大学,2006.
[13]A.Kemnitz,M.Marangio.[r,s,t]-colorings of graphs.Discrete Mathematics,2007,307:199-207.
[14]Liu Linzhong,Li Yinzgen,Zhang Zhongfu.On the adjacent strong edge coloring of Halin graph.Journal of Mathematical Research & Exposition,2003,23(2):241-246.
[15] Liu Linzhong, Zhang Zhongfu, Wang jianfang . On the vertex strong total coloring for Halin graphs with △(G)≤5. Mathmatics In Economics, 2002, 19(1): 77-80.
[16] Weibin, Liu Linzhong, Zhang Zhongfu. On the Agjacent strong edge coloring for Halin graphs with △(G) = 4. Mathmatics In Economics, 2001, 18(4): 82-85.
[17] Andrzej Czygrinow, Brendan Nagle. Strong edge colorings of uniform graphs. Discrete Mathematics, 2004, 286: 291-223.
[18] A. Nadolski. The circular chromatic index of some class 2 graphs. Discrete Mathematics, 2007, 307: 1447-1454.
[19] Zhang Zhongfu, Liu Linzhong. On the complete chromatic number of Halin graph. Acata Math. Appl. Sinica, 1997, 13(1): 102-106.
[20] Zhang Zhongfu, Liu Linzhong , Wang jianfang. On the strong edge coloring of outer plane graphs. Journal of Mathematical Research & Exposition, 2005, 25(2): 255-266.
[21] M. Mollly, B. Reed. A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B, 1997, 69: 103-109.
[22] Liu Linzhong, Xie Jiguo and Zhang Zhongfu. On the vertex strong total coloring of graphs. Mathematics In Dconomics, 1998, 15(3): 52-55.
[23] Zhang Zhongfu, Zhang Jianxun, Wang Jianfang. The total chromatic number of some graphs. Sci.Sinica, Ser. A, 1988, 31(12): 1434-1441.
[24] P. N. Balister, B. Bollobas, R. H. Schelp. Vertex distinguishing colorings of graphs with △(G) = 2. Discrete Mathematics, 2002, 252: 17-29.
[25] C.N.Campos, C. p. de Mello. The total chromatic number of some bipartite graphs. Electronic Notes in Discrete Mathematics, 2005, 22: 557-561.
[26] P. N. Balister, E. Gyori, J.Lehel, R. H. Schelp, Adjacent vertex distinguishing Edge- Colorings. Discrete Mathematics, 2007, 21(1): 237-250.
[27] H.Wang. On the adjacent vertex distinguishing total chromatic numbers of graphs with △(G) = 3. J. Combin. Optim, 2007, 14: 87-109.
[28] Armen S. Asratiana, C. J. Casselgrenb. On interval edge colorings of (α,β)-biregular bipartite graphs. Discrete Mathematics, 2006, 307: 1951-1956.
[29] P.Wittmann. Vertex-distinguishing edge-colorings of 2- regular graphs. Discrete Mathematics, 1997, 79: 265-277.
[30]严谦泰,冉红.P_n~k的均匀全染色.大学数学,2007,23(3):59-64.
[31]张忠辅,强会英.关于C_n~4∨C_n~5(n≡0(mod5))的邻强边色数.兰州交通大学学报,2005,6(24):133-135.
[32]赵新梅,陈祥恩.单圈图的邻强边染色.兰州交通大学学报,2005,24(6):0138-0140.
[33]陈祥恩,张忠辅.P_m∨P_n的邻点可区别全染色.西北师范大学学报,2005,41(1):13-15.
[34]马明,刘华等.P_n∨P_m的邻点可区别边染色.经济数学,2005,22(2):215-219.
[35]包世堂,赵传成等.P_m∨K_n的点可区别边染色.甘肃高师学报,2004,9(5):16-17.
[36]晁福刚,强会英,闫丽宏.P_m∨S_n的邻点可区别全染色.经济数学,2005,22(3):327-330.
[37]陈克斌,李秦,等桂梅.星和完全等二部图联图的邻强边染色.石河子大学学报,2006,24(5):657-660.
[38]刘利群,陈祥恩.一类联图的点可区别正常边染色.西北师范大学学报(自然科学版),2006,42(5):21-25.
[39]马少仙,马刚,张忠辅.路与星联图的点可区别边染色.山东科技大学学报,2005,24(3):90-93.
[40]唐国梅,马刚,马少仙.关于P_m∨S_n的邻点可区别全染色.华东交通大学学报,2006,23(5):133-135.
[41]仇鹏翔,程耀东.关于P_n∨K_(n,n)的邻强边染色.兰州交通大学学报,2006,25(4):143-146.
[42]仇鹏翔,程耀东,田双亮.星和完全等二部图联图的点可区别均匀边染色.数学的实践与认识,2007,37(22):165-172.
[43]张忠辅,李敬文,赵传成等.若干联图的点可区别均匀边色数.数学学报,2007,50(1):197-204.
[44]马刚,刘华,唐国梅等.圈和扇的联图的全染色.华东交通大学学报,2005,4(22):152-154.
[45]田双亮.若干联图的邻点可区别全染色.西北民族大学学报,2006,1:0005-0007.
[46]王继顺,邱泽阳,张忠辅.联图的邻点可区别全染色.应用数学学报,2006,29(5):879-844.
[47]董海燕,孙磊.几类有趣图的邻点可区别全染色.山东科学,2006,19(2):9-10.
[48]王颜妮,王丽伟,刘萍.几类图的邻点可区别的全染色.科学技术与工程,2007,7(13):3048-3051.
[49]张忠辅,陈祥恩,李敬文等.关于图的邻点可区别全染色.中国科学A辑数学,2004,34(5):574-583.
[50]王朝瑞,图论.北京理工大学出版社,2000.
[51]卢开澄,图论及其应用.清华大学出版社,1981.
[52]陈子歧,朱必文,刘峙山.图论.高等教育出版社,1990.
[53]哈拉里F.图论[M].上海:上海科学技术出版社,1980.