关于平面图的全染色的几个结果
|
摘要
对图论的研究已经有二百多年的历史,最早关于图论的文章是在1736年由欧拉完成的,该文章解决了著名的哥尼斯城堡七桥问题.自20世纪六十年代以来,图论得到了迅猛发展,图论方面的结果大量涌现,其中图的染色理论在图论研究中占有重要的地位,图的染色理论在最优化、计算机理论、网络设计等方面有着重要的应用.本文旨在讨论平面图的全染色.
本文讨论的图均为简单无向有限的平面图.对于一个图G=G(V(G),E(G),ψ_G),V(G),E(G)分别表示其顶点集合和边的集合,ψ_G为点和边的关联函数.对于顶点v∈V(G),我们用d(v)表示其度数,△(G)和δ(G)分别表示G中顶点的最大度和最小度,简记为△和δ.在图论符号中我们常略去字母G分别用V,E,v和ε代替V(G),E(G),v(G),ε(G).
若图G可以表示在平面上,并且任两条边仅在其端点处才可能相交,则称G是可平面图.图G的这种平面上的表示方法称为G的一个平面嵌入,或称平面图.一个平面图G把平面划分为若干个连通区域,这些区域的闭包称为G的面,图G所有的面构成的集合记为F.一个面f∈F所关联的边的个数(割边计算两次)称为面f的度,用d(f)或r(f)表示.若G的两个面有一条公共边,则称这两个面相邻.如果G是连通的平面图,则有|V|-|E|+|F|=2(Euler公式).
根据一定的规则将一组目标划分为不同的种类,这是数学中的一个基本方法.不同的规则决定着该组中任意一对目标是否在同一类中.图的染色理论就是研究这类问题的一门理论,它有着相当广泛的应用背景.各种形式的日程表问题、时间表问题以及排序问题,从根本上来说都可以归结为染色问题.
图G的全k染色是指至多用k种颜色,对G的顶点和边同时染色,使得相邻的两个元素(点和点,边和边,点和边)染以不同的颜色.图G的全色数x_T(G)是指G的全k染色中最小的正整数k.如果一个图G的全色数x_T(G)=△(G)+1,则称G为第一类图.对于G的全色数x_T(G),已有的结果可以总结为:
(1)对△(G)≠6的平面图,有χ_T(G)≤△(G)+2;
(2)对△(G)≥9的平面图,有χ_T(G)=△(G)+1
本文对平面图的全染色进行了讨论.全文共分三章.第一章介绍了图论中的一些基本概念,综述了当前全染色理论的主要研究成果和本文的一些主要结果.第二章我们考虑最大度较小的平面图的全染色.Behzad和Vizing分别对全染色进行了研究,提出了下面的猜想:
猜想对任意图G,都有△(G)+1≤x_T(G)≤△(G)+2.该猜想被称为全染色猜想.
本章的主要结论为:
如果平面图G的最大度△(G)≥5,并且G既不含4-圈也不含5-圈,则
第三章中提出了图的最优全染色与强度的定义,并得到了几类平面图的全染色和与强度.
Graph theory has been well studied for more than 200 years. The first graph theory paper, which resolved the well known Seven Bridges of K(?)nigsberg problem, was written by Euler in 1736. From 1960s, graph theory has developed rapidly. A large number of results were presents by scientist. One of most important research field in graph theory is coloring. It has widely applied in many areas like optimization theory, computer science, and network design. This paper mainly focuses on the total coloring of planar graph.
All graphs mentioned in this paper are simple undirected finite planar graph. Given a graph G = G(V(G),E(G),ψ_G),V(G),E{G) represent its vertex set and edge set respectively,ψ_G is the adjacent function of vertex and edge. For any vertex v∈V(G), d(v) is its degree,△(G) andδ(G)are the maximum degree and minimum degree,△andδin short. For symbols in graph theory, we usually omit the letter G and use V,E,v and s replaceV(G),E(G),v(G),s(G).
Graph G is planer if it can be drawn on a plane, and any two edges intersect only on their adjacent vertex. Such kind of presentation of graph G on plane is called planar embed of G or planar graph. A graph was divided into several connected fields, and the closures of these fields were defined as faces of G. F is the set composed by all of these faces. The number of edges adjacent with a given face f∈F is the degree of f (cut will be countedtwice), named r(f). If two faces of graph G share an edge, we say these two faces are adjacent. If G is a connected planar graph, then there is |V|-|E|+|F|= 2 (Euler formula).
Classifying a group of object into several catalogs rely on a given ruler is a fundamental strategy in mathematics. Different ruler gives different results. The coloring theory in graph theory is a case of this kind of study. It has been widely used in practice. For example, Schedule problem, Bin packing problem and sorting problem can be deduced to coloring problem.
The total k coloring of graph G is that, using at most k colors to color the vertex and edges of G, so that any two adjacent elements (vertex and edge, vertex and vertex, edge and edge) have different colors. The total chromatic number x_T(G) is the minimum positive integral k among all k coloring of graph. If x_T(G)=△(g)+1 , then G is class 1 graph. For x_T(G), there are some results as following:
(1)If△(G)≠6,thenχ_T(G)≤△(G)+2;
(2) If△(G)≥9, thenχ_T(G)=△(G)+1.
This paper discussed the total coloring of planar graph. The paper has 3 chapters. The first chapter introduced some basic definition in graph theory, and summarized current results in total coloring and the main results in this paper. In chapter 2, we studied the total coloring of planar graph with smaller maximum degree. Behzad and Vizinghave the following conjecture related to total coloring:
Total coloring Conjecture: For any graph G ,△(G)+1≤x_T(G)≤△(G)+2.
The main results in this chapter is:
For planar graph G, if maximum degree△(G)≥5, and G has no 4-cycle and 5-cycle,
The last chapter gave the definition of optimized total coloring and strength, and presented the total coloring and strength of several catalogs of planar graph.
本文讨论的图均为简单无向有限的平面图.对于一个图G=G(V(G),E(G),ψ_G),V(G),E(G)分别表示其顶点集合和边的集合,ψ_G为点和边的关联函数.对于顶点v∈V(G),我们用d(v)表示其度数,△(G)和δ(G)分别表示G中顶点的最大度和最小度,简记为△和δ.在图论符号中我们常略去字母G分别用V,E,v和ε代替V(G),E(G),v(G),ε(G).
若图G可以表示在平面上,并且任两条边仅在其端点处才可能相交,则称G是可平面图.图G的这种平面上的表示方法称为G的一个平面嵌入,或称平面图.一个平面图G把平面划分为若干个连通区域,这些区域的闭包称为G的面,图G所有的面构成的集合记为F.一个面f∈F所关联的边的个数(割边计算两次)称为面f的度,用d(f)或r(f)表示.若G的两个面有一条公共边,则称这两个面相邻.如果G是连通的平面图,则有|V|-|E|+|F|=2(Euler公式).
根据一定的规则将一组目标划分为不同的种类,这是数学中的一个基本方法.不同的规则决定着该组中任意一对目标是否在同一类中.图的染色理论就是研究这类问题的一门理论,它有着相当广泛的应用背景.各种形式的日程表问题、时间表问题以及排序问题,从根本上来说都可以归结为染色问题.
图G的全k染色是指至多用k种颜色,对G的顶点和边同时染色,使得相邻的两个元素(点和点,边和边,点和边)染以不同的颜色.图G的全色数x_T(G)是指G的全k染色中最小的正整数k.如果一个图G的全色数x_T(G)=△(G)+1,则称G为第一类图.对于G的全色数x_T(G),已有的结果可以总结为:
(1)对△(G)≠6的平面图,有χ_T(G)≤△(G)+2;
(2)对△(G)≥9的平面图,有χ_T(G)=△(G)+1
本文对平面图的全染色进行了讨论.全文共分三章.第一章介绍了图论中的一些基本概念,综述了当前全染色理论的主要研究成果和本文的一些主要结果.第二章我们考虑最大度较小的平面图的全染色.Behzad和Vizing分别对全染色进行了研究,提出了下面的猜想:
猜想对任意图G,都有△(G)+1≤x_T(G)≤△(G)+2.该猜想被称为全染色猜想.
本章的主要结论为:
如果平面图G的最大度△(G)≥5,并且G既不含4-圈也不含5-圈,则
第三章中提出了图的最优全染色与强度的定义,并得到了几类平面图的全染色和与强度.
Graph theory has been well studied for more than 200 years. The first graph theory paper, which resolved the well known Seven Bridges of K(?)nigsberg problem, was written by Euler in 1736. From 1960s, graph theory has developed rapidly. A large number of results were presents by scientist. One of most important research field in graph theory is coloring. It has widely applied in many areas like optimization theory, computer science, and network design. This paper mainly focuses on the total coloring of planar graph.
All graphs mentioned in this paper are simple undirected finite planar graph. Given a graph G = G(V(G),E(G),ψ_G),V(G),E{G) represent its vertex set and edge set respectively,ψ_G is the adjacent function of vertex and edge. For any vertex v∈V(G), d(v) is its degree,△(G) andδ(G)are the maximum degree and minimum degree,△andδin short. For symbols in graph theory, we usually omit the letter G and use V,E,v and s replaceV(G),E(G),v(G),s(G).
Graph G is planer if it can be drawn on a plane, and any two edges intersect only on their adjacent vertex. Such kind of presentation of graph G on plane is called planar embed of G or planar graph. A graph was divided into several connected fields, and the closures of these fields were defined as faces of G. F is the set composed by all of these faces. The number of edges adjacent with a given face f∈F is the degree of f (cut will be countedtwice), named r(f). If two faces of graph G share an edge, we say these two faces are adjacent. If G is a connected planar graph, then there is |V|-|E|+|F|= 2 (Euler formula).
Classifying a group of object into several catalogs rely on a given ruler is a fundamental strategy in mathematics. Different ruler gives different results. The coloring theory in graph theory is a case of this kind of study. It has been widely used in practice. For example, Schedule problem, Bin packing problem and sorting problem can be deduced to coloring problem.
The total k coloring of graph G is that, using at most k colors to color the vertex and edges of G, so that any two adjacent elements (vertex and edge, vertex and vertex, edge and edge) have different colors. The total chromatic number x_T(G) is the minimum positive integral k among all k coloring of graph. If x_T(G)=△(g)+1 , then G is class 1 graph. For x_T(G), there are some results as following:
(1)If△(G)≠6,thenχ_T(G)≤△(G)+2;
(2) If△(G)≥9, thenχ_T(G)=△(G)+1.
This paper discussed the total coloring of planar graph. The paper has 3 chapters. The first chapter introduced some basic definition in graph theory, and summarized current results in total coloring and the main results in this paper. In chapter 2, we studied the total coloring of planar graph with smaller maximum degree. Behzad and Vizinghave the following conjecture related to total coloring:
Total coloring Conjecture: For any graph G ,△(G)+1≤x_T(G)≤△(G)+2.
The main results in this chapter is:
For planar graph G, if maximum degree△(G)≥5, and G has no 4-cycle and 5-cycle,
The last chapter gave the definition of optimized total coloring and strength, and presented the total coloring and strength of several catalogs of planar graph.
引文
1.Behzad M.Graphs and their chromatic numbers[D], Michigan State University, 1965
2.Vizing V G. On an estimate of the Chromatis class of a p-graph(in Russian)[J], Diskret. Analisz, 1964,3:25-30
3.Sanchez-Arroyo A.Determining the total coloring number is NP-hard[J], Discrete Math. 1989,78:315-319
4.Rosenfeld M.On the total coloring of certain graphs[J], Is tael Math. 1971,9:396-402
5.Kostochka A. V. The total coloring of a mutigraph with maximal degree 4[J], Discrete Math, 1977,17:161-163
6.Kostochka A. V. The total chromatic number of any mutigraph with maximal degree five is at most seven [J], Discrete Math., 1996,162:199-214
7.Yap H P,Wang Jian-Fang and Zhang Zhongfu.Total chromatic number of raphs of high degree [J], J.Australian Math.Soc,(Ser.A), 1989,47:445-452
8.Hilton A J W, Hind H R.Total chromatic number of graphs having large maximum Degree[J], Discrete Math. 1993,117:127-140
9.Yap H P.Total coloring of graphs,Lecture Notes in Mamthematics,(1623)[M]. Berlin: Springer, 1996
10.Sanders D P.,Zhao Y.On totai 9-coloring planar of maximum degree seven[J], Journal of Graph Theory, 1999,31:67-73
11.Wang Ping,Wu Jian-Liang. A note on total colorings of planar graph without 4-cycles[J]. Discussiones Mathematicae Graph Theory, 2004,24:125-135
12.默帝USR.图论及其应用[M],吴望名等译.北京,科学出版社,1984
13.O.V.Borodin,Kostochka A.V.Woodall D.R.total colorings of planar graphs with large maximum degree[J], Journal og Graph Theory, 1997,26:53-59
14.Borodin,Kostochka A.V.Woodall D.R. List edge and list total colorings of multigraphs[J], Journal of Combin.Theory(B) 1997,71:184-204
15.Vizing V G. Vertex colouring with given colours (in Russian)[J], Metody Diskret Analiz, 1976,29:3-10
16.A.J.W.Hilton and Zhao Cheng.The relationship between an edge-colouring conjecture and a total colouring conjecture[J], J.Combin.Math.Combin,Comput, 1991,10:83-95
17.Andersen L.Total colouring of simple graphs[D], DENMARK:University of Aalborg, 1993
18.Gross, Tucker T.W.Topological Graph Theory[M], New York, Jhon and WilerySons, 1987
19.T.R.Jensen,B.Toft.Graph Coloring Problems.[M],New York John and Wilery &Sons, 1995
20.孙向勇,关于3-圈不重点的平面图全染色的一个结论.[J],山东大学学报,2006,21(4):374-376
21.K.Appel,W.Haken and J.Koch.Every planar map is four colorable[J], Part2, Reducibility, Illinois J.Math.21,1977,491-567
22.Weifan Wang. On the coloring of outerplanar graphs Discrete athematics[J], Discrete mathmetic 1995,257-269
23.Daniel P.Sanders and Yue Zhao.Planar Graphs of Maximum Degree Seven are Class I[J], Comb.Theory,Series B, 2001, 83:201-212
24.Z.Zhang, J.Zhang and J.wang,The total chromatic number of some graphs[J], Scientia Sinica, 1988,31:1434-1441
25.O.V.Borodin, D.R.Woodall. Thirteen Colouring Numbers for Outerplane Graphs[J], European Journal of Combinatics, 1998,19(1):19-24
26.Shen Lan,Wang Ying Qian,Tota colorings of planar graphs with maximum degree at least 8[J], Sciencien China,ser .A Mathematics, 2008,52(4): 561-564
27.M.Chen, Y.Q.Wang.A note on totally colouring of plane graphs[J],Journal of Zhejiang Normal University,(Natural Science), 2007,30:421-423 28. J.F.Hou,G.Z.Liu,J.S.Cai.List edge and list total coloring of planar graphs without 4-cycles[J], Theoretical Computer Sciences, 2006,369: 250-255
29.Wang Y Q,Shangguan M L ,Li Q.On total chromatic number of planar graphs without 4-cycles[J], Sciencien China,ser.A Mathematics, 2007,50: 81-86
30.Wu jian-Liang. Some results on edge colorings of graphs[J],山东大学学报(自然版), 1999,34(2):121-124
31.B.Mohar and C .Thomassen. Graphs on surfaces[M], The Johns Hopkins. Univ.Press, Baltimore, 2001
32.Ewa. Kubicka and Allen J. Schwenk. An introduction to chromatic sums[A], Proc. ACM Computer Science Conference (Louisville)[C]. 1989,39-45
33.C Thomassen, P Erdos, Y Alavi. Malde and Allen J.Schwenk. Tight Bounds on the Chromatic Sum of a Connected Graph[J], Journal of Graph Theory,1989,13(3):353-357
34.Krzysztof Giaro, Marek Kubale. Edge-chromatic sum of trees and bounded cyclicity graphs[J], Informmation Processing Letters, 2000,75:65-69
35.H. Hajiabolhassan, M.L. Mehrabadi, R. Tusserkani. Minimal coloring and strength of graphs[J], Discrete Math, 2000,215:265-270
36.Mohammad R.Salavatipour. On sum coloring of graphs[J], Discrete Applied Math, 2003,127:477-488
37.Michal Malaflejski, Krzysztof Giaro,Robert Janczewski and Marek Kubale. Sum coloring of bipartite graphs with bounded degree[J], Algorithmica,2004,40:235-244
38.H. Hajiabolhassan, M. L Mehrabadi, and R. Tusserkani. Tabular graphs and chromatic sum [J], Discrete Math, 2005,304:11-22
2.Vizing V G. On an estimate of the Chromatis class of a p-graph(in Russian)[J], Diskret. Analisz, 1964,3:25-30
3.Sanchez-Arroyo A.Determining the total coloring number is NP-hard[J], Discrete Math. 1989,78:315-319
4.Rosenfeld M.On the total coloring of certain graphs[J], Is tael Math. 1971,9:396-402
5.Kostochka A. V. The total coloring of a mutigraph with maximal degree 4[J], Discrete Math, 1977,17:161-163
6.Kostochka A. V. The total chromatic number of any mutigraph with maximal degree five is at most seven [J], Discrete Math., 1996,162:199-214
7.Yap H P,Wang Jian-Fang and Zhang Zhongfu.Total chromatic number of raphs of high degree [J], J.Australian Math.Soc,(Ser.A), 1989,47:445-452
8.Hilton A J W, Hind H R.Total chromatic number of graphs having large maximum Degree[J], Discrete Math. 1993,117:127-140
9.Yap H P.Total coloring of graphs,Lecture Notes in Mamthematics,(1623)[M]. Berlin: Springer, 1996
10.Sanders D P.,Zhao Y.On totai 9-coloring planar of maximum degree seven[J], Journal of Graph Theory, 1999,31:67-73
11.Wang Ping,Wu Jian-Liang. A note on total colorings of planar graph without 4-cycles[J]. Discussiones Mathematicae Graph Theory, 2004,24:125-135
12.默帝USR.图论及其应用[M],吴望名等译.北京,科学出版社,1984
13.O.V.Borodin,Kostochka A.V.Woodall D.R.total colorings of planar graphs with large maximum degree[J], Journal og Graph Theory, 1997,26:53-59
14.Borodin,Kostochka A.V.Woodall D.R. List edge and list total colorings of multigraphs[J], Journal of Combin.Theory(B) 1997,71:184-204
15.Vizing V G. Vertex colouring with given colours (in Russian)[J], Metody Diskret Analiz, 1976,29:3-10
16.A.J.W.Hilton and Zhao Cheng.The relationship between an edge-colouring conjecture and a total colouring conjecture[J], J.Combin.Math.Combin,Comput, 1991,10:83-95
17.Andersen L.Total colouring of simple graphs[D], DENMARK:University of Aalborg, 1993
18.Gross, Tucker T.W.Topological Graph Theory[M], New York, Jhon and WilerySons, 1987
19.T.R.Jensen,B.Toft.Graph Coloring Problems.[M],New York John and Wilery &Sons, 1995
20.孙向勇,关于3-圈不重点的平面图全染色的一个结论.[J],山东大学学报,2006,21(4):374-376
21.K.Appel,W.Haken and J.Koch.Every planar map is four colorable[J], Part2, Reducibility, Illinois J.Math.21,1977,491-567
22.Weifan Wang. On the coloring of outerplanar graphs Discrete athematics[J], Discrete mathmetic 1995,257-269
23.Daniel P.Sanders and Yue Zhao.Planar Graphs of Maximum Degree Seven are Class I[J], Comb.Theory,Series B, 2001, 83:201-212
24.Z.Zhang, J.Zhang and J.wang,The total chromatic number of some graphs[J], Scientia Sinica, 1988,31:1434-1441
25.O.V.Borodin, D.R.Woodall. Thirteen Colouring Numbers for Outerplane Graphs[J], European Journal of Combinatics, 1998,19(1):19-24
26.Shen Lan,Wang Ying Qian,Tota colorings of planar graphs with maximum degree at least 8[J], Sciencien China,ser .A Mathematics, 2008,52(4): 561-564
27.M.Chen, Y.Q.Wang.A note on totally colouring of plane graphs[J],Journal of Zhejiang Normal University,(Natural Science), 2007,30:421-423 28. J.F.Hou,G.Z.Liu,J.S.Cai.List edge and list total coloring of planar graphs without 4-cycles[J], Theoretical Computer Sciences, 2006,369: 250-255
29.Wang Y Q,Shangguan M L ,Li Q.On total chromatic number of planar graphs without 4-cycles[J], Sciencien China,ser.A Mathematics, 2007,50: 81-86
30.Wu jian-Liang. Some results on edge colorings of graphs[J],山东大学学报(自然版), 1999,34(2):121-124
31.B.Mohar and C .Thomassen. Graphs on surfaces[M], The Johns Hopkins. Univ.Press, Baltimore, 2001
32.Ewa. Kubicka and Allen J. Schwenk. An introduction to chromatic sums[A], Proc. ACM Computer Science Conference (Louisville)[C]. 1989,39-45
33.C Thomassen, P Erdos, Y Alavi. Malde and Allen J.Schwenk. Tight Bounds on the Chromatic Sum of a Connected Graph[J], Journal of Graph Theory,1989,13(3):353-357
34.Krzysztof Giaro, Marek Kubale. Edge-chromatic sum of trees and bounded cyclicity graphs[J], Informmation Processing Letters, 2000,75:65-69
35.H. Hajiabolhassan, M.L. Mehrabadi, R. Tusserkani. Minimal coloring and strength of graphs[J], Discrete Math, 2000,215:265-270
36.Mohammad R.Salavatipour. On sum coloring of graphs[J], Discrete Applied Math, 2003,127:477-488
37.Michal Malaflejski, Krzysztof Giaro,Robert Janczewski and Marek Kubale. Sum coloring of bipartite graphs with bounded degree[J], Algorithmica,2004,40:235-244
38.H. Hajiabolhassan, M. L Mehrabadi, and R. Tusserkani. Tabular graphs and chromatic sum [J], Discrete Math, 2005,304:11-22