Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-24T15:39:16.315Z 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: [email protected])
JIANFENG HOU*
Affiliation:
Center for Discrete Mathematics, Fuzhou University, Fujian 350116, China (e-mail: [email protected])
XINGXING YU
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: [email protected])
*
[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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