Please wait a minute...
北京大学期刊网 | 作者  审稿人  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 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

[398 KB]


摘要 图的划分问题是图论研究中最重要的一个问题之一, 图论研究的很多问题都是特殊形式的划分问题, 比如经典染色理论要求将图划分成最少的独立集, 而最大 k-部子图问题则是要找图中边数最多的一个 k-部子图. 本文给出划分问题的一些最新进展, 以及一些尚未解决的问题, 其中大部分是来自于求最大k-部子图的相关领域.
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: Combinatorial
Optimization (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.
Full text



首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录

© 2015-2017 北京大学图书馆 .