北京大学期刊网　|　作者　　审稿人　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 2016, Vol. 45(1): 1-20
 综述文章
 图的划分: 一些进展与未解决问题 Graph Partitions: Recent Progresses and Some Open Problems 许宝刚 XU Baogang 南京师范大学数学科学学院数学研究所, 南京, 江苏, 210023 Institute of Mathematics, School of Mathematical Sciences, Nanjing Normal University, Nanjing, Jiangsu, 210023, P. R. China 收稿日期: 2015-01-04 2016, Vol. 45(1): 1-20 DOI: 10.11845/sxjz.2015001a
 PDF [398 KB] 1335 下载 581 浏览 引用导出

Abstract：Graph partition problem is one of the most important topics in structural graph theory, since many problems in graph theory can be treated as a partition of the vertices into sets with some properties. For instance, the classical vertex coloring problem asks for a partition into minimum number of independent sets, and the maximum k-partite subgraph problem asks for a k-partite subgraph with maximum number of edges. In this paper, we present some results and problems on graph partitions, of which most are from the topic originated from the maximum k-partite subgraph problem.
 PACS: O157.5
 [1] Alon, N., Bipartite subgraphs, {it Combinatorica, 1996, 16(3): 301-311.[2] Alon, N., Bollob'{as, B., Krivelevich, M. and Sudakov, B., Maximum cuts and judicious partitions in graphs without short cycles, {it J.Combin.Theory Ser.B, 2003, 88(2): 329-346.[3] Alon, N. and Milman, V.D., lambda_1, isoperimetric inequalities for graphs, and superconcentrators, {it J.Combin. Theory Ser.B, 1985, 38(1): 73-88.[4] Arkin, E.M. and Hassin, R., Graph partitions with minimum degree constraints, {it Discrete Math., 1998, 190(1/2/3): 55-65.[5] Ban, A. and Linial, N., Internal partitions of regular graphs, {it J. Graph Theory, 2015, doi: 10.1002/jgt.21909, in press.[6] Barahona, F., The max-cut problem on graphs not contractible to K_5, {it Oper.Res.Lett., 1983, 2(3): 107-111.[7] Barahona, F., Grotschel, M., J unger, M. and Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout design, {it Oper.Res., 1988, 36(3): 493-513.[8] Bauer, F. and Jost, J., Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator, {it Comm.Anal.Geom., 2013, 21(4): 787-845.[9] Bazgan, C., Tuza, Z. and Vanderpooten, D., Efficient algorithms for decomposing graphs under degree constraints, {it Discrete Appl.Math., 2007, 155(8): 979-988.[10] Bollob'{as, B., Extremal Graph Theory, London: Academic Press, 1978.[11] Bollob'{as, B. and Scott, A.D., Judicious partitions of graphs, {it Period.Math.Hungar., 1993, 26(2): 125-137.[12] Bollob'{as, B. and Scott, A.D., Exact bounds for judicious partitions of graphs, {it Combinatorica, 1999, 19(4): 473-486.[13] Bollob'{as, B. and Scott, A.D., Problems and results on judicious partitions, {it Random Structures Algorithms, 2002, 21(3/4): 414-430.[14] Bollob'{as, B. and Scott, A.D., Better bounds for max cut, In: Contemporary Combinatorics (Bollobas, B. ed.), Bolyai Soc.Math.Stud., Vol.10, Berlin: Springer-Verlag, 2002, 185-246.[15] Bollob'{as, B. and Scott, A.D., Judicious partitions of bounded-degree graphs, {it J. Graph Theory, 2004, 46(2): 131-143.[16] Bondy, J.A. and Locke, S.C., Largest bipartite subgraphs in triangle-free graphs with maximum degree three, {it J. Graph Theory, 1986, 10(4): 477-504.[17] Chang, K.C., Cheeger's constant and spectrum of the 1-Laplacian on graphs, a plenary talk at the 6th Conference of Chinese Combinatorics and Graph Theory Society, Guangzhou, 2014.[18] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, In: Problems in Analysis (Papers Dedicated to Salomon Bochner, 1969, Gunning, R.C. ed.),Princeton: Princeton Univ.Press, 1970, 195-199.[19] Chen, G.T., Gould, R.J. and Yu, X.X., Graph connectivity after path removal, {it Combinatorica, 2003, 23(2): 185-203.[20] Diwan, A.A., Decomposing graphs with girth at least five under degree constraints, {it J. Graph Theory, 2000, 33(4): 237-239.[21] Dodziuk, J., Difference equations, isoperimetric inequality and transience of certain random walks, {it Trans. Amer.Math. Soc., 1984, 284(2): 787-794.[22] Edwards, C.S., Some extremal properties of bipartite subgraphs, {it Canad. J. Math., 1973, 25(3): 475-485.[23] Edwards, C.S., An improved lower bound for the number of edges in a largest bipartite subgraph, In: Recent Advances in Graph Theory (Fiedler, M. ed.), Prague: Academia, 1975, 167-181.[24] ErdH{os, P., Problems and results in graph theory and combinatorial analysis, In: Graph Theory and Related Topics (Bondy, J.A. and Murty, U.S.R. eds.), New York: Academic Press, 1979, 153-163.[25] ErdH{os, P., Faudree, R., Pach, J. and Spencer, J., How to make a graph bipartite, {it J.Combin.Theory Ser.B, 1988, 45(1): 86-98.[26] ErdH{os, P., Some recent problems in combinatorics and graph theory, a lecture at the 26th Southeastern International Conference on Graph Theory, Combinatorics and Computing, Boca Raton, 1995.[27] Fan, G.H., Hou, J.F. and Zeng, Q.H., A bound for judicious k-partitions of graphs, {it Discrete Appl.Math., 2014, 179: 86-99.[28] Fan, G.H., Xu, B.G., Yu, X.X. and Zhou, C.X., Upper bounds on minimum balanced bipartitions, {it Discrete Math., 2012, 312(6): 1077-1083.[29] Gerber, M.U. and Kobler, D., Classes of graphs that can be partitioned to satisfy all their vertices, {it Australas. J. Combin., 2004, 29: 201-214.[30] Goemans, M.X. and Williamson, D.P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,{it J. ACM, 1995, 42(6): 1115-1145.[31] Hadlock, F.O., Finding a maximum cut of a planar graph in polynomial time, {it SIAM J. Comput., 1975, 4(3): 221-225.[32] Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, {it Combinatorica, 1983, 3(1): 95-99.[33] Hopkins, G. and Staton, W., Extremal bipartite subgraphs of cubic triangle-free graphs, {it J. Graph Theory, 1982, 6(2): 115-121.[34] Hu, X.L., Zhang, Y.Q. and Chen, Y.J., A note on almost balanced bipartitions of a graph, {it Bull.Aust.Math. Soc., 2015, 91(2): 177-182.[35] Kaneko, A., On decomposition of triangle-free graphs under degree constraints, {it J. Graph Theory, 1998, 27(1): 7-9.[36] Karawabayashi, K., Lee, O., Reed, B. and Wollan, P., A weaker version of Lov'{asz' path removal conjecture, {it J. Combin. Theory Ser. B, 2008, 98(5): 972-979.[37] Karpinski, M., Approximability of the minimum bisection problem: an algorithmic challenge, In: Mathematical Foundations of Computer Science 2002 (Diks, K. and Rytter, W. eds.), Lecture Notes in Comput. Sci., Vol. 2420, Berlin: Springer-Verlag, 2002, 59-67.[38] Kriesell, M., Induced paths in 5-connected graphs, {it J. Graph Theory, 2001, 36(1): 52-58.[39] K uhn, D. and Osthus, D., Partitions of graphs with high minimum degree or connectivity, {it J. Combin. Theory Ser. B, 2003, 88(1): 29-43.[40] Lee, C., Loh, P.S. and Sudakov, B., Bisections of graphs, {it J.Combin.Theory Ser.B, 2013, 103(5): 599-629.[41] Lee, J.R., Gharan, S.O. and Trevisan, L., Multi-way spectral partitioning and higher-order Cheeger inequalities, In: STOC '12 (Proceedings of the 44th Annual ACM Symposium on Theory of Computing), New York, 2012, 1117-1130.[42] Li, G.N. and Xu, B.G., Some results of regular graphs on the existence of balanced partition, {it Appl.Math. J. Chinese Univ.Ser.A, 2009, 24(3): 353-358 (in Chinese).[43] Li, H.Y., Liang, Y.T., Liu, M.H., and Xu, B.G., On minimum balanced bipartitions of triangle-free graphs, {it J.Comb.Optim., 2014, 27(3): 557-566.[44] Li, R. and Xu, B.G., On a graph partition result of K uhn and Osthus, {it Ars Combin., 2012, 103: 491-495.[45] Liu, M.H. and Xu, B.G., Bipartition of graph under degree constrains, {it Sci.China Math., 2015, 58(4): 869-874.[46] Liu, M.H. and Xu, B.G., On judicious partitions of graphs, {it J.Comb.Optim., 2014, doi: 10.1007/s10878-015-9828-3, in press.[47] Liu, M.H. and Xu, B.G., On partitions of graphs under degree constrains, submitted.[48] Liu, S.P., Multi-way dual Cheeger constants and spectral bounds of graphs, {it Adv. Math., 2015, 268: 306-338.[49] Locke, S.C., Maximum k-colorable subgraphs, {it J. Graph Theory, 1982, 6(2): 123-132.[50] Ma, J. and Yu, X.X., Bounds for pairs in partitions of graphs, {it Discrete Math., 2010, 310(15/16): 2069-2081.[51] Ma, J. and Yu, X.X., On judicious bipartitions of graphs, {it Combinatorica, 2014, in press.[52] Mader, W., Existenz n-fach zusammenh angender teilgraphen in graphen gen ugend gro{sser Kantendichte, {it Abh. Math.Semin.Univ.Hambg., 1972, 37(1/2): 86-97 (in German).[53] Maurer, S.B., Vertex colorings without isolates, {it J. Combin.Theory Ser.B, 1979, 27(3): 294-319.[54] Miclo, L., On eigenfunctions of Markov processes on trees, {it Probab.Theory Related Fields, 2008, 142(3/4): 561-594.[55] Poljak, S. and Tuza, Zs., Bipartite subgraphs of triangle-free graphs, {it SIAM J. Discrete Math., 1994, 7(2): 307-313.[56] Poljak, S. and Tuza, Zs., Maximum cuts and large bipartite subgraphs, In: CombinatorialOptimization (Papers From the DIMACS Special Year) (Cook, W., Lov'asz, L. and Seymour, P.D. eds.), DIMACS Ser. Discrete Math. Theoret.Comput.Sci., Vol.20, Providence, R.I.: AMS, 1995, 181-244.[57] Potter, T.D., On a bottleneck bipartition conjecture of ErdH{os, {it Combinatorica, 1992, 12(3): 317-321.[58] Scott, A.D., Judicious partitions and related problems, In: Survey in Combinatorics, 2005 (Webb, B.S. ed.), London Math. Soc.Lecture Note Ser., Vol.327,Cambridge: Cambridge Univ.Press, 2005, 95-118.[59] Shahrokhi, F. and Sz'{ekely, L.A., The complexity of the bottleneck graph bipartition problem, {it J.Combin. Math.Combin.Comput., 1994, 15: 221-226.[60] Shearer, J.B., A note on bipartite subgraphs of triangle-free graphs, {it Random Structures Algorithms, 1992, 3(2): 223-226.[61] Staton, W., Edge deletions and the chromatic number, {it Ars Combin., 1980, 10: 103-106.[62] Stiebitz, M., Decomposing graphs under degree constraints, {it J. Graph Theory, 1996, 23(3): 321-324.[63] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, {it J. Graph Theory, 1983, 7(2): 165-167.[64] Trevisan, L., Max cut and the smallest eigenvalue, {it SIAM J. Comput., 2012, 41(6): 1769-1786.[65] Xu, B.G., Yan, J. and Yu, X.X.,Balanced judicious bipartitions of graphs, {it J. Graph Theory, 2010, 63(3): 210-225.[66] Xu, B.G., Yan, J. and Yu, X.X., A note on balanced bipartitions,{it Discrete Math., 2010, 310(20): 2613-2617.[67] Xu, B.G. and Yu, X.X., Triangle-free subcubic graphs with minimum bipartite density, {it J. Combin.Theory Ser.B, 2008, 98(3): 516-537.[68] Xu, B.G. and Yu, X.X., On a bipartition problem of Bollob'as and Scott, {it Combinatorica, 2009, 29(5): 595-618.[69] Xu, B.G. and Yu, X.X., Judicious k-partitions of graphs, {it J. Combin.Theory Ser.B, 2009, 99(2): 324-337.[70] Xu, B.G. and Yu, X.X., Better bounds for k-partitions of graphs, {it Combin.Probab.Comput., 2011, 20(4): 631-640.[71] Xu, B.G. and Yu, X.X., On judicious bisections of graphs, {it J. Combin.Theory Ser.B, 2014, 106: 30-69.[72] Yannakakis, M., Node- and edge-deletion NP-complete problems, In: STOC '78 (Proceedings of the 10th Annual ACM Symposium on Theory of Computing), New York, 1978, 253-264.[73] Zhu, X.D., Bipartite density of triangle-free subcubic graphs, {it Discrete Appl.Math., 2009, 157(4): 710-714.[74] Zhu, X.D., Bipartite subgraphs of triangle-free subcubic graphs, {it J. Combin.Theory Ser.B, 2009, 99(1): 62-83.
 [1] 周倩楠, 王力工, 卢勇. 关于哈密顿图和可迹图的一些充分条件[J]. 数学进展, 2018, 47(1): 31-40. [2] 文飞, 黄琼湘, 马小玲. 一类图的谱半径与特征多项式[J]. 数学进展, 2018, 47(1): 41-50. [3] 李建喜, 常安. 图的规范拉普拉斯特征值的上界[J]. 数学进展, 2018, 47(1): 51-55. [4] 潘文华, 徐常青. 无$K_4$-图子式的图的邻和可区别边染色[J]. 数学进展, 2017, 46(6): 839-847. [5] 刘颖, 沈建. 关于图的规范拉普拉斯特征值和的若干结果[J]. 数学进展, 2017, 46(6): 848-856. [6] 朱雪琴,田贵贤,崔淑玉. 局部剖分邻接冠图的谱[J]. 数学进展, 2017, 46(5): 673-681. [7] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354. [8] 单治超. 有限随机图上的随机游动和传染病模型[J]. 数学进展, 2017, 46(1): 1-12. [9] 王力工, 孙丰妹. 单圈图的无符号拉普拉斯埃斯特拉达指数[J]. 数学进展, 2017, 46(1): 47-54. [10] 冯荣权, 曾丽伟. 有向强正则图及其构造[J]. 数学进展, 2016, 45(6): 817-839. [11] 崔淑玉,田贵贤. 图的各类矩阵表示的谱半径的界[J]. 数学进展, 2016, 45(5): 711-720. [12] 李玉萍, 孟吉翔, 孙星红. 极大非正则图的边数[J]. 数学进展, 2016, 45(5): 721-726. [13] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490. [14] 李晓艳，陈敏，王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499. [15] 姚京京, 邵泽玲, 徐常青. \mbox{\boldmath $\Delta=3$} 的图的邻和可区别全可选性[J]. 数学进展, 2016, 45(3): 343-348.
Viewed
Full text

Abstract

Cited

Discussed