Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-06T20:26:02.094Z Has data issue: false hasContentIssue false
  • English
  • Français

Bisections of Graphs Without Short Cycles

Part of: Graph theory

Published online by Cambridge University Press:  28 September 2017

GENGHUA FAN ,
JIANFENG HOU  and
XINGXING YU
GENGHUA FAN
Affiliation:
Center for Discrete Mathematics, Fuzhou University, Fujian 350116, China (e-mail: fan@fzu.edu.cn)
JIANFENG HOU*
Affiliation:
Center for Discrete Mathematics, Fuzhou University, Fujian 350116, China (e-mail: fan@fzu.edu.cn)
XINGXING YU
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: yu@math.gatech.edu)
*
jfhou@fzu.edu.cn
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Bollobás and Scott (Random Struct. Alg.21 (2002) 414–430) asked for conditions that guarantee a bisection of a graph with m edges in which each class has at most (1/4+o(1))m edges. We demonstrate that cycles of length 4 play an important role for this question. Let G be a graph with m edges, minimum degree δ, and containing no cycle of length 4. We show that if (i) G is 2-connected, or (ii) δ ⩾ 3, or (iii) δ ⩾ 2 and the girth of G is at least 5, then G admits a bisection in which each class has at most (1/4+o(1))m edges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollobás, Krivelevich and Sudakov shows that for infinitely many m there exists a graph with m edges and girth at least 5 for which any bisection has at least (1/4−o(1))m edges in one of the two classes.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C75: Structural characterization of families of graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 1 , January 2018 , pp. 44 - 59
Copyright
Copyright © Cambridge University Press 2017 

Footnotes

†

Partially supported by NSFC grant 11331003.

‡

Corresponding author. Partially supported by NSFC grant 11671087.

§

Partially supported by NSF grants DMS-1265564 and DMS-1600738, and by the Hundred Talents Program of Fujian Province.

References

[1] Alon, N. (1996) Bipartite subgraphs. Combinatorica 16 301–311.CrossRefGoogle Scholar
[2] Alon, N., Bollobás, B., Krivelevich, M. and Sudakov, B. (2003) Maximum cuts and judicious partitions in graphs without short cycles. J. Combin. Theory Ser. B 88 329–346.CrossRefGoogle Scholar
[3] Bollobás, B. and Scott, A. D. (1997) Judicious partitions of hypergraphs. J. Combin. Theory Ser. A 78 15–31.CrossRefGoogle Scholar
[4] Bollobás, B. and Scott, A. D. (1999) Exact bounds for judicious partitions of graphs. Combinatorica 19 473–486.Google Scholar
[5] Bollobás, B. and Scott, A. D. (2002) Problems and results on judicious partitions. Random Struct. Alg. 21 414–430.CrossRefGoogle Scholar
[6] Bollobás, B. and Scott, A. D. (2002) Better bounds for Max Cut. In Contemporary Combinatorics, Vol. 10 of Bolyai Society Mathematical Studies, pp. 185–246.Google Scholar
[7] Bondy, A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97–105.CrossRefGoogle Scholar
[8] Edwards, C. S. (1973) Some extremal properties of bipartite graphs. Canad. J. Math. 3 475–485.CrossRefGoogle Scholar
[9] Edwards, C. S. (1975) An improved lower bound for the number of edges in a largest bipartite subgraph. In Proc. 2nd Czechoslovak Symposium on Graph Theory, pp. 167–181.Google Scholar
[10] Erdős, P., Gyárfás, A. and Kohayakawa, Y. (1997) The size of the largest bipartite subgraphs. Discrete Math. 177 267–271.CrossRefGoogle Scholar
[11] Fan, G. and Hou, J. (2017) Bounds for pairs in judicious partitioning of graphs. Random Struct. Alg. 50 59–70.CrossRefGoogle Scholar
[12] Hou, J. and Zeng, Q. (2017) Judicious partitioning of hypergraphs with edges of size at most 2. Combin. Probab. Comput. 26 267–284.CrossRefGoogle Scholar
[13] Lee, C., Loh, P. and Sudakov, B. (2013) Bisections of graphs. J. Combin. Theory Ser. B 103 590–629.CrossRefGoogle Scholar
[14] Lu, C., Wang, K. and Yu, X. (2015) On tight components and anti-tight components. Graphs Combin. 31 2293–2297.CrossRefGoogle Scholar
[15] Ma, J., Yen, P. and Yu, X. (2010) On several partitioning problems of Bollobás and Scott. J. Combin. Theory Ser. B 100 631–649.CrossRefGoogle Scholar
[16] Ma, J. and Yu, X. (2016) On judicious bipartitions of graphs. Combinatorica 36 537–556.CrossRefGoogle Scholar
[17] Poljak, S. and Tuza, Z. (1994) Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math. 7 307–313.CrossRefGoogle Scholar
[18] Scott, A. D. (2005) Judicious partitions and related problems. In Surveys in Combinatorics, Vol. 327 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 95–117.Google Scholar
[19] Xu, B., Yan, J. and Yu, X. (2010) Balanced judicious partitions of graphs. J. Graph Theory 63 210–225.CrossRefGoogle Scholar
[20] Xu, B., Yan, J. and Yu, X. (2010) A note on balanced bipartitions. Discrete Math. 310 2613–2617.CrossRefGoogle Scholar
[21] Xu, B. and Yu, X. (2008) Triangle-free subcubic graphs with minimum bipartite density. J. Combin. Theory Ser. B 98 516–537.CrossRefGoogle Scholar
[22] Xu, B. and Yu, X. (2009) Judicious k-partition of graphs. J. Combin. Theory Ser. B 99 324–337.CrossRefGoogle Scholar
[23] Xu, B. and Yu, X. (2011) Better bounds for k-partitions of graphs. Combin. Probab. Comput. 20 631–640.CrossRefGoogle Scholar
[24] Xu, B. and Yu, X. (2014) On judicious bisection of graphs. J. Combin. Theory Ser. B 106 30–69.CrossRefGoogle Scholar
[25] Zhu, X. (2009) Bipartite density of triangle-free subcubic graphs. Discrete Appl. Math. 157 710–714.CrossRefGoogle Scholar