摘要
图的染色是图论研究的重要内容,在现代计算机科学、信息科学等领域有着十分广泛的的应用,一直得到国内外同行的极大关注.本学位论文主要围绕着图的六大染色问题展开,即:无圈点列表染色、星染色、Injective染色、点荫度、分数染色以及边面全染色.除了分析探讨图的自身结构之外,我们主要运用著名的Discharging方法来研究平面图的染色问题.
在第一章,我们给出本文所用到的基本概念,简述了相关领域的研究现状,并给出本文的主要结果.
在第二章,我们着重研究平面图的无圈点列表染色问题.此类问题最早(2002)是由Borodin, Fon-Der Flaass, Kostochka, Raspaud和Sopena引入和研究的.他们证明了每个平面图是无圈7-点列表可染的,并且提出了极具挑战性的猜想:每个平面图是无圈5-点列表可染的.我们在第二章中给出目前最接近此猜想的结果,并且还得到了平面图无圈3-点列表染色以及4-点列表染色的充分条件.
在第三章,我们将集中精力研究Subcubic图的星色数.利用对Subcubic图的结构分析,我们证明了:每个Subcubic图是6-星-可染的.需要说明的是:这个结果是最好可能的,因为Fertin, Raspaud和Reed已经给出了Wagner图不是5-星-可染的结论.
在第四章,我们将主要探讨K_4-minor-free图的Injective色数问题.图G的点染色被称作是Injective的,如果任意点v的邻点颜色互不相同.我们将证明:每个非空的K4-minor-free图G的Injective色数最多是-32-(G)-.此结果,当-(G)为偶数时,是最好可能的,因为存在一个非空的K4-minor-free图H(-(H)为偶数)的Injective色数恰好为-23-(H)-.另外,我们还给出了一般平面图的Injective色数上界.
一个非平凡图G的点荫度va(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来,图的点荫度问题的研究成为图论的一个焦点.在第五章,我们将完全解决Raspaud和Wang提出的猜想:每个不包含相交三角形的平面图的点荫度最多是2.
在第六章,我们将通过研究Sparse图与Petersen图的同构关系来讨论Sparse图的分数染色.证明了每个无3-圈且最大平均度小于5/2的图是(5,2)-可染色的.我们将通过反例说明:条件“无3-圈”和“最大平均度小于5/2”都是必不可少的.
最后,在第七章,我们讨论了平面图的边面全染色问题. 2001年, Sanders和Zhao提出了极具挑战性的猜想:每个平面图G是((?)(G) + 2)-边面全染色的,并且先后解决了(?)≥7和(?)≤3的情况.迄今为止, (?)∈{4,5,6}的情形仍然是开放的.作为本学位论文的亮点之一,我们彻底解决了(?)(G) = 6的情况.
Graph coloring is an important ?eld in Graph theory. It has wide applicationsin modern computer science and information science. In this thesis, we are interestedin various coloring problems of graphs, including acyclic list coloring, star coloring,injective coloring, vertex-arboricity, fractional coloring and edge-face coloring. Themain method we will use in this thesis is Discharging argument.
In Chapter 1, we collect some basic notions used in the thesis and give a chiefsurvey in each direction. Our main results will be stated.
In Chapter 2, we mainly consider the acyclic list coloring of planar graphs. Thisnotion was ?rstly introduced (2002) by Borodin, Fon-Der Flaass, Kostochka, Raspaud,and Sopena. They proved that every planar graph is acyclically 7-list colorable. More-over, they proposed a challenging conjecture: every planar graph is acyclically 5-listcolorable. We will, in Chapter 2, show our result which is the best approach to thisconjecture. In addition, we obtain some su?cient conditions for planar graphs to beacyclically 3-list colorable or acyclically 4-list colorable.
In Chapter 3, we focus on the star chromatic number of subcubic graphs. Bya more complex analysis of the structure of subcubic graphs, we prove that everysubcubic graph is 6-star-colorable. This result is best possible, since Fertin, Raspaudand Reed showed that the Wagner graph cannot be 5-star-colorable.
In Chapter 4, we will investigate the injective chromatic number of K4-minor-free graphs. A vertex coloring of G is called injective, if every vertex v∈V , allthe neighbors of v are assigned with distinct colors. We shall prove that every non- empty K_4-minor-free graph G hasχi(G)≤32(G), whereχi(G) denotes the injectivechromatic number of G. This result is best possible when (G) even in the sense thatthere exist K4-minor-free graphs G withχi(G) = 23(G). Moreover, we will show ageneral upper bound on injective colorings of planar graphs.
The vertex-arboricity va(G) of a graph G is the minimum number of subsets intowhich vertex set V (G) can be partitioned so that each subsets induces a forest. Re-cently, studying vertex-arboricity of graphs becomes a very popular topic. In Chapter5, we completely solved a conjecture of Raspaud and Wang asserting that every planargraph without intersecting triangles has vertex-arboricity at most 2.
In Chapter 6, we will give the fractional chromatic number of sparse graphs bystudying the homomorphism problems of sparse graphs to the Petersen graph. Moreprecisely, we prove that every triangle-free graph with maximum average degree lessthan 5/2 is (5, 2)-colorable. Moreover, we show that the conditions“triangle-free”and“maximum average degree less than 5/2”are necessary.
Finally, in Chapter 7, we will discuss the edge-face coloring of planar graphs. In2001, Sanders and Zhao proposed a challenge conjecture: every planar graph G is edge-face ((G) + 2)-colorable, and left the case∈{4, 5, 6} unsolved. In this chapter, weshall settle the case (G) = 6.
引文
[1] M. O. Albertson, D. M. Berman, Every planar graph has an acyclic 7-coloring,Israel J. Math., 28 (1977), 169-174.
[2] M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Ku¨ndgen, R. Ramamurthi,Coloring with no 2-colored P4’s, Electron. J. Combin., 11 (2004), R26.
[3] Y. Alavi, D. Green, J. Liu, J. Wang, On linear vertex-arboricity of graphs, Congres.Numer., 82 (1991), 187-192.
[4] K. Appel, W. Haken, The existence of unavoidable sets of geographically goodcon?gurations, Illinois J. Math., 20 (1976), 218-297.
[5] Y. Alavi, J. Liu, J. Wang, On linear vertex-arboricity of complementary graphs,J. Graph Theory, 18 (1994), 315-322.
[6] N. Alon, M. Tarsi, Coloring and orientations of graphs, Combinatorica, 12 (1992),125-134.
[7] S. A. Burr, An inequality involving the vertex arboricity and the edge arborocityof a graph, J. Graph Theory, 10 (1986), 403-404.
[8] O. V. Borodin, On acyclic coloring of planar graphs, Discrete Math., 25 (1979),211-236.
[9] O. V. Borodin, Simultaneous coloring of edges and faces of plane graphs, DiscreteMath., 128 (1994), 21-33.
[10] O. V. Borodin, Acyclic 4-colorability of planar graphs without 4- and 5-cycles,Diskretn. Anal. Issled. Oper., 17 (2010), 20-38. (in Russian)
[11] O. V. Borodin, M. Chen, A. O. Ivanova, A. Raspaud, Acyclic 3-choosability ofsparse graphs with girth at least 7, Discrete Math., 310 (2010), 2426-2434.
[12] Y. Bu, N. W. Cranston, M. Montassier, A. Raspaud, W. Wang, Star-coloring ofsparse graphs, J. Graph Theory, 62 (2009), 201-219.
[13] Y. Bu, D. Chen, A. Raspaud, W. Wang, Injective coloring of plane graphs, DiscreteAppl. Math., 157 (2009), 663-672.
[14] O. V. Borodin, D. G. Fon-Der Flaass, A. V. Kostochka, A. Raspaud, E. Sopena,Acyclic list 7-coloring of planar graphs, J. Graph Theory, 40 (2002), 83-90.
[15] O .V. Borodin,S. G. Hartke, A. O. Ivanova, A. V. Kostochka, D. B. West, (5, 2)-coloring of Sparse Graphs, Sib. Elektron. Mat. Izv., 5 (2008), 417-426.
[16] O. V. Borodin, A. O. Ivanova, Planar graphs without triangular 4-cycles are 4-choosable,, Sib. Elektron. Mat. Izv., 5 (2008), 75-79.
[17] O. V. Borodin, A. O. Ivanova, List 2-arboricity of planar graphs with no trianglesat distance less than two, Sib. Elektron. Mat. Izv., 5 (2008), 211-214.
[18] O. V. Borodin, A. O. Ivanova, Planar graphs without 4-cycles adjacent to 3-cyclesare list vertex 2-arboricity, J. Graph theory, 62 (2009), 234-240.
[19] O. V. Borodin, A. O. Ivanova, Acyclic 5-choosability of planar graphs withoutadjacent short cycles, To appear in J. Graph Theory, 2011.
[20] O. V. Borodin, A. O. Ivanova, Acyclic 4-choosability of planar graphs with no 4-and 5-cycles, Submitted for publication, 2010.
[21] O. V. Borodin, A. O. Ivanova, A. Raspaud, Acyclic 4-choosability of planar graphswith neither 4-cycles nor triangular 6-cycles, Discrete Math., 310 (2010), 2946-2950.
[22] O. V. Borodin, A. O. Ivanova, A. V. Kostochka, Oriented vertex 5-coloring ofsparse graphs, Anal. Issled. Oper. Ser., 13 (2006), 16-32. (in Russian)
[23] O. V. Borodin, S. -J. Kim, A. V. Kostochka, D. B. West, Homomorphisms fromsparse graphs with large girth, J. Combin. Theory Ser. B, 90 (2004), 147-159.
[24] O. V. Borodin, A. V. Kostochka, B. Toft, Variable degeneracy: extensions ofBrooks’and Gallai’s theorems, Discrete Math., 214 (2000), 101-112.
[25] O. V. Borodin, A. V. Kostochka, D. R. Woodall, Acyclic colourings of planargraphs with large girth, J. London Math. Soc., 60 (1999), 344-352.
[26] J. A. Bondy, U. S. R Murty, Graph Theory with Applications, New York: Macmil-lan, 1976.
[27] R. J. Cook, Point-arboricity and girth, J. London Math. Soc., 8 (1974), 322-324.
[28] G. J. Chang, C. Chen, Y. Chen, Vertex and tree arboricities of graphs, J. Combin.Optim., 8 (2004), 295-306.
[29] Z. Chen, X. He, Parallel complexity of partitioning a planar graph into vertex-induced forests, Discrete Appl. Math., 69 (1996), 183-198.
[30] G. Chartrand, H. V. Kronk, The point-arboricity of planar graphs, J. LondonMath. Soc., 44 (1969), 612-616.
[31] M. Chen, G. Hahn, A. Raspaud, W. Wang, On the injective coloring of K4-minorfree graphs, To appear in J. Comb. Optim., 2011.
[32] G. Chartrand, H. V. Kronk, C. E. Wall, The point-arboricity of a graph, Israel J.Math., 6 (1968), 169-175.
[33] M. Chen, A. Raspaud, Planar graphs without 4, 5 and 8-cycles are acyclically4-choosable, Electron. Notes in Discrete Math., 34 (2009), 659-667.
[34] M. Chen, A. Raspaud, On acyclic 4-choosability of planar graphs without shortcycles, Discrete Math., 310 (2010), 2113-2118.
[35] M. Chen, A. Raspaud, Homomorphisms from sparse graphs to the Petersen graph,Discrete Math., 310 (2010), 2705-2713.
[36] M. Chen, A. Raspaud, A su?cient condition for planar graphs to be acyclically5-choosable, To appear in J. Graph Theory, 2011.
[37] M. Chen, A. Raspaud, Planar graphs without 4- and 5-cycles are acyclically 4-choosable, Submitted for publication, 2010.
[38] M. Chen, A. Raspaud, N. Roussel, X. Zhu, Acyclic 4-choosability of planar graphs,Discrete Math., 311 (2011), 92-101.
[39] M. Chen, A. Raspaud, W. Wang, Star list chromatic number of planar subcubicgraphs, Submitted for publication, 2010.
[40] M. Chen, A. Raspaud, W. Wang, 6-star-coloring of subcubic graphs, Submittedfor publication, 2010.
[41] M. Chen, A. Raspaud, W. Wang, Vertex-arboricity of planar graphs without in-tersecting triangles, To appear in Europ. J. Comb., 2011.
[42] M. Chen, A. Raspaud, W. Wang, Plane graphs with maximum degree 6 are edge-face 8-colorable, Submitted for publication, 2010.
[43] M. Chen, W. Wang, Acyclic 5-choosability of planar graphs without 4-cycles,Discrete Math., 308 (2008), 6216-6225.
[44] R. J. Du?n, Topology of series-parallel networks, J. Math. Anal. Appl., 10 (1965),303-318.
[45] A. Doyon, G. Hahn, A. Raspaud, Some bounds on the injective chromatic numberof graphs, Discrete Math., 310 (2010), 585-590.
[46] Z. Dvoˇra′k, R. Sˇkrekovski, T. Valia, Planar graphs of odd-girth at least 9 arehomomorphic to the Petersen graph, SIAM J. Discrete Math., 22 (2008), 568-591.
[47] P. Erd?os, A. L. Rubin, H. Taylor, Choosability in graphs, Congr. Numer., 26(1979), 125-157.
[48] B. Farzad, Planar graphs without 7-cycles are 4-choosable, SIAM J. DiscreteMath., 23 (2009), 1179-1199.
[49] Fiamˇc′?k, Simultaneous colouring of 4-valent, Mat. Cˇs., 21 (1971), 7-13.
[50] G. Fijavˇz, M. Juvan, B. Mohar, R. Sˇkrekovski, Planar graphs without cycles ofspeci?c lengths, Europ. J. Combin., 23 (2002), 377-388.
[51] G. Fertin, A. Raspaud, B. Reed, On star-coloring of graphs, Lecture Notes inComput. Sci., 2204 (2001), 140-153.
[52] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. TheorySer. B, 63 (1995), 153-158.
[53] W. Goddard, Acyclic colorings of planar graphs, Discrete Math., 91 (1991), 91-94.
[54] B. Gru¨nbaum, Acyclic colorings of planar graphs, Israel J. Math., 14 (1973), 390-408.
[55] S. Gutner, The complexity of planar graph choosability, Discrete Math., 159(1996), 119-130.
[56] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theoryof NP-Completeness, W. H. Freeman and Company, New York, 1979.
[57] G. Hahn, J. Kratochv′il, J. Sˇir′anˇ, D. Sotteau, On the injective chromatic numberof graphs, Discrete Math., 256 (2002), 179-192.
[58] P. Hell, J. Ne?set?ril, Graphs and homomorphisms, Oxford university press, NewYork, 2004.
[59] S. L. Hakimi, E. F. Schmeichel, A note on the vertex arboricity of a graph, SIAMJ. Discrete Math., 2 (1989), 64-67.
[60] D. Huang, W. Wang, Vertex arboricity of planar graphs without chordal 6-cycles,Submitted for publication, 2010.
[61] F. Jaeger, On circular ?ows in graphs, in Finite and In?nite Sets, Colloq. Math.Soc. J′anos Bolyai 37, North Holland, Amsterdam, 391-402, 1984.
[62] E. Jucoviˇc, On a problem in map coloring, Mat. Cˇs., 19 (1969), 225-227.
[63] A. V. Kostochka, Acyclic 6-coloring of planar graphs, Metody Diskret. Anal., 28(1976), 40-56. (in Russian)
[64] H. A. Kierstead, A. Ku¨ndgen, C. Timmons, Star coloring bipartite planar graphs,J. Graph Theory, 60 (2009), 1-10.
[65] A. V. Kostochka, L. S. Mel’nikov, Note to the paper of Gru¨nbaum on acycliccolorings, Discrete Math., 14 (1976), 403-406.
[66] S. J. Kim, S. Oum, Injective chromatic number and chromatic number of thesquare of graphs, Submitted for publication, 2009.
[67] R.J. Kang, J-S. Sereni, M. Stehl′?k, Every plane graph of maximum degree 8 hasand edge-face 9-colouring, Submitted for publication, 2010.
[68] A. Ku¨ndgen, C. Timmons, Star coloring planar graphs from small lists, J. GraphTheory, 63 (2010), 324-337.
[69] W. Klostermeyer, C. Q. Zhang, N-tuple colouring of planar graphs with large oddgirth, Graphs and Combin., 18 (2002), 119-132.
[70] B. Luzar, R. Sˇkrekovski, M. Tancer, Injective colorings of planar graphs with fewcolors, Discrete Math., 309 (2009), 5636-5649.
[71] P. C. B. Lam, B. Xu, J. Liu, The 4-choosability of plane graphs without 4-cycles,J. Combin. Theory Ser. B, 76 (1999), 117-126.
[72] K. W. Lih, W. Wang, X. Zhu, Coloring the square of a K4-minor free graph,Discrete Math., 269 (2003), 303-309.
[73] Peter C. B. Lam, B. Xu, J. Liu, The 4-choosability of plane graphs without 4-cycles, J. Combin Theory Ser B, 76 (1999), 117-126.
[74] R. Luo, C.-Q. Zhang, Edge-face chromatic number and edge chromatic number ofsimple plane graphs, J. Graph Theory, 49 (2005), 234-256.
[75] M. Matsumoto, Bounds for the vertex linear arboricity, J. Graph Theory, 14(1990), 117-126.
[76] J. Mitchem, Every planar graph has an acyclic 8-coloring, Duke Math. J., 41(1974), 177-181.
[77] L. S. Melnikov, Problem 9, in: M. Fiedler (Ed.), Recent Advances in Graph The-ory, Proceedings of the Second Czechoslovak Symposium, Prague, June, 1974,Academia, Prague, Czechoslovak, 1975, p. 543.
[78] M. Mirzakhani, A small non-4-choosable planar graph, Bull. Inst. Combin. Appl.,17 (1996), 15-18.
[79] M. Montassier, Colorations de graphes sous contraintes, Conception de r′eseauxembarqu′es tol′erants aux pannes, Ph. D. Thesis, Universit′e de Bordeaux, France,2005.
[80] M. Montassier, A smaller not 3-choosable planar graph without 4- and 5-cycles,Technical Report RR-1361-05, Universit′e de Bordeaux, LaBRI, 2005.
[81] M. Montassier, Acyclic 4-choosability of planar graphs with girth at least 5, Trendsin Mathematics: Graph Theory in Paris, 299-310, 2007.
[82] M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J.Graph Theory, 51 (2006), 281-300.
[83] M. Montassier, A. Raspaud, W. Wang, Acyclic 4-choosability of planar graphswithout cycles of speci?c lengths, Topics in discrete mathematics, AlgorithmsCombinatorics, Springer, Berlin, 26 (2006), 473-491.
[84] M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphswithout small cycles, J. Graph Theory, 54 (2007), 245-260.
[85] J. Ne?set?ril, P. Ossana de Mendez, Colorings and homomorphisms of minor closedclasses, Discrete and Computational Geometry: The Goodman-Pollack Festschrift,17 (2003), 651-664.
[86] K. S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory, 14(1990), 73-75.
[87] A. Pirnazar, D. H. Ullman, Girth and fractional chromatic number of planargraphs, J. Graph Theory, 39 (2002), 201-217.
[88] A. Raspaud, E. Sopena, Good and semi-strong colorings of oriented planar graphs,Inform. Process. Lett., 51 (1994), 171-174.
[89] A. Raspaud, W. Wang, On the vertex-arboricty of planar graphs, Europ. J. Com-bin., 29 (2008), 1064-1075.
[90] S. K. Stein, B-Sets and planar maps, Pacific. J. Math., 37 (1971), 217-224.
[91] R. S?krekovski, On the critical point-arboricity graphs, J. Graph Theory, 39 (2002),50-61.
[92] E. R. Scheinerman, D. H. Ullman, Fractional graph theory, Wiley-interscience,1997.
[93] D. P. Sanders, Y. Zhao, On simultaneous edge-face colorings of plane graphs,Combinatorica, 17 (1997), 441-445.
[94] D. P. Sanders, Y. Zhao, A ?ve-color theorem, Discrete Math., 220 (2000), 279-281.
[95] D. P. Sanders, Y. Zhao, On improving the edge-face coloring theorem, Graphs andCombin., 17 (2001), 329-341.
[96] M. Tarsi, On the decomposition of a graph into stars, Discrete Math., 36 (1981),299-304.
[97] C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B, 62(1994), 180-181.
[98] C. Thomassen, 3-List-coloring planar graphs of girth 5, J. Combin. Theory Ser.B, 64 (1995), 101-107.
[99] C. Timmons, Star-coloring planar graphs, Master’s Thesis, California State Uni-versity San Marcos, USA, 2007.
[100] C. Timmons, Star coloring high girth planar graphs, Electron. J. Combin., 15(2008), R124.
[101] W. T. Tutte, On hamiltonian circuits, J. London Math. Soc., 21 (1946), 98-101.
[102] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J.Math., 6 (1954), 80-91.
[103] W. T. Tutte, On the imbeddings of linear graphs in surfaces, Proc. London Math.Soc., 51 (1954), 474-483.
[104] V. G. Vizing, Vertex coloring with given colors, Metody Diskret. Anal., 29 (1976),3-10. (in Russian)
[105] A. Vince, Star chromatic number, J. Graph Theory, 12 (1988), 551-559.
[106] M. Voigt, List colourings of planar graphs, Discrete Math., 120 (1993), 215-219.
[107] M. Voigt, A non-3-choosable planar graph without cycles of length 4 and 5,Discrete Math., 307 (2007), 1013-1015.
[108] A. O. Waller, Simultaneously coloring the edges and faces of plane graphs, J.Combin. Theory Ser. B, 69 (1997), 219-221.
[109] J. Wang, On point-linear arboricity of planar graph, Discrete Math., 72 (1988),381-384.
[110] G. Wegner, Note on a paper by B.Grunbaum on acyclic colorings, Israel J. Math.,14 (1973), 409-412.
[111] D. B. West, Introduction to Graph Theory, Pearson Education, Inc, 2002.
[112] W. Wang, M. Chen, Planar graphs without 4-cycles are acyclically 6-choosable,J. Graph Theory, 61 (2009), 307-323.
[113] W. Wang, K. W. Lih, The 4-choosability of planar graphs without 6-cycles, Aus-tralas J. Combin., 24 (2001), 157-164.
[114] W. Wang, K. W. Lih, Choosability and edge choosability of planar graphs without?ve cycles, Appl. Math. Lett., 15 (2002), 561-565.
[115] W. Wang, K.-W. Lih, A new proof of Melnikov’s conjecture on the edge-facecoloring of plane graphs, Discrete Math., 253 (2002), 87-95.
[116] W. Wang, K. W. Lih, Choosability and edge choosability of planar graphs withoutintersection triangles, SIAM J. Discrete Math., 15 (2003), 538-545.
[117] W. Wang, K.-W. Lih, The edge-face choosability of plane graphs, Europ. J.Comb., 25 (2004), 935-948.
[118] X. Zhu, Circular chromatic number: a survey, Discrete Math., 229 (2001), 371-410.
[119] X. Zhu, Circular chromatic number of planar graphs of large odd girth, Electron.J. Combin., 8 (2001), R25.
[120] H. Zhang, B. Xu, Acyclic 5-choosability of planar graphs with neither 4-cyclesnor chordal 6-cycles, Discrete Math., 309 (2009), 6087-6091.