[1]林晶.不含H子图的图上的最大割下界[J].福建工程学院学报,2020,18(01):87-91.[doi:10.3969/j.issn.1672-4348.2020.01.016]
　LIN Jing.Lower bounds on maximum cuts in H-free graphs[J].Journal of FuJian University of Technology,2020,18(01):87-91.[doi:10.3969/j.issn.1672-4348.2020.01.016]
点击复制

不含H子图的图上的最大割下界()
分享到：

《福建工程学院学报》[ISSN:2097-3853/CN:35-1351/Z]

卷:
第18卷
期数:
2020年01期
页码:
87-91
栏目:
出版日期:
2020-02-25

文章信息/Info

Title:
Lower bounds on maximum cuts in H-free graphs
作者:
林晶
福建工程学院数理学院
Author(s):
LIN Jing
Mathematics and Physics Institute, Fujian University of Technology
关键词:
最大割;  不含H子图;  下界
Keywords:
maximum cut;  H-free graphs;  lower bound
分类号:
O157.5
DOI:
10.3969/j.issn.1672-4348.2020.01.016
文献标志码:
A
摘要:
文章证明了对于由单个顶点连接任意t个点不交的完全二部图K2，s的所有顶点构成的图H，有f(m，H)≥m2+Ω(m(2t+1)/(3t+1))；特别当t=1时，该猜想近似成立。还证明了对于轮图W2k，有f(m，W2k)≥m2+Ω(m(2k+2)/(3k+2))。
Abstract:
This paper shows that, for any graph H obtained by connecting a single vertex to all vertices of the union of t vertex-disjoint K2,s, f（m,H）≥〖SX(〗m〖〗2〖SX)〗+Ω（m(2t+1)/(3t+1)）. In particular, the conjecture is confirmed asymptotically for t=1. It is also proved that for any wheel graph W2k, f（m,W2k）≥〖SX(〗m〖〗2〖SX)〗+Ω（m(2k+2)/(3k+2)）

参考文献/References:

[1] EDWARDS C. An improved lower bound for the number of edges in a largest bipartite subgraph[C]∥Proc 2nd Czechoslovak Symposium on Graph Theory, 1975: 167-181.[2] ALON N. Bipartite subgraphs[J]. Combinatorica, 1996, 16 (3): 301-311.[3] ALON N, HALPERIN E. Bipartite subgraphs of integer weighted graphs[J]. Discrete Mathematics, 1998, 181 (1/2/3): 19-29.[4] BOLLOBS B, SCOTT A. Problems and results on judicious partitions[J]. Random Structures & Algorithms, 2002, 21 (3/4): 414-430.[5] SCOTT A. Judicious partitions and related problems[M]∥WEBB B S. Surveys in Combinatorics 2005. Cambridge: Cambridge University Press, 2005: 95-118.[6] BOLLOBS B, SCOTT A. Max k-cut and judicious k-partitions [J]. Discrete Mathematics, 2010, 310 (15/16): 2126-2139.[7] ALON N, BOLLOBS B, KRIVELEVICH M, et al. Maximum cuts and judicious partitions in graphs without short cycles[J], Journal of Combinarorial Theory: Series B, 2003, 88(2): 329-346.[8] ERDS P. Problems and results in graph theory and comobinatorial analysis[M]∥Graph Theory and Related Topics. New York: Academic Press, 1979: 153-163.[9] 〖ZK(〗POLJAK S, TUZA Z. Bipartite subgraphs of triangle-free graphs[J]. SIAM Journal on Discrete Mathematics, 1994, 7(2): 307-313.[10] SHEARER J. A note on bipartite subgraphs of triangle-free graphs[J]. Random Structures & Algorithms, 1992, 3(2): 223-226.[11] ALON N, KRIVELEVICH M, SUDAKOV B. Maxcut in H-free graphs[J]. Combinatorics, Probability and Computing, 2005, 14(5/6): 629-647.[12] ZENG Q, HOU J. Bipartite subgraphs of H-free graphs[J]. Bulletin of the Australian Mathematical Society, 2017, 96: 1-13.[13] ZENG Q, HOU J. Maximum cuts of graphs with forbidden cycles[J]. Ars Mathematica Contemporanea, 2018, 15(1): 147-160.[14] LOCKE S. Maximum k-colorable subgraphs[J]. Journal of Graph Theory, 1982, 6(2): 123-132.[15] ERDS P, GYRFS A, KOHAYAKAWA Y. The size of the largest bipartite subgraphs[J]. Discrete Mathematics, 1997, 177 (1/2/3): 267-271.[16] ALON N, KRIVELEVICH M, SUDAKOV B. Turn numbers of bipartite graphs and related Ramseytype questions[J]. Combinatorics, Probability and Computing, 2003, 12(5/6): 477-494.[17] BONDY A, SIMONOVITS M. Cycles of even length in graphs[J]. Journal of Combinarorial Theory: Series B, 1974, 16(2): 97-105.

更新日期/Last Update: 2019-02-25