For a graph G, let f(G) denote the maximum number of edges in a bipartite subgraph of G. For an integer m ≥ 1 and for a set ℋ of graphs, let f(m, ℋ) denote the minimum possible cardinality of f(G), as G ranges over all graphs on m edges that contain no member of ℋ as a subgraph. In particular, for a given graph H, we simply write f(m, H) for f(m, ℋ) when ℋ = {H}. Let r > 4 be a fixed even integer. Alon et al. (2003) conjectured that there exists a positive constant c(r) such that f(m, Cr − 1) ≥ m/2 + c(r)mr/(r + 1) for all m. In the present article, we show that f(m, Cr − 1) ≥ m/2 + c(r)(mrlog4m)1/(r + 2) for some positive constant c(r) and all m. For any fixed integer s ≥ 2, we also study the function f(m, ℋ) for ℋ = {K2, s, C5} and ℋ = {C4, C5, …, Cr − 1}, both of which improve the results of Alon et al.
@article{1218,
title = {Maximum cuts of graphs with forbidden cycles},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {15},
year = {2018},
doi = {10.26493/1855-3974.1218.5ed},
language = {EN},
url = {http://dml.mathdoc.fr/item/1218}
}
Zeng, Qinghou; Hou, Jianfeng. Maximum cuts of graphs with forbidden cycles. ARS MATHEMATICA CONTEMPORANEA, Tome 15 (2018) . doi : 10.26493/1855-3974.1218.5ed. http://gdmltest.u-ga.fr/item/1218/