Name
Abstract | ||
|---|---|---|
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 H of graphs, let f(m, H) denote the minimum possible cardinality of f(G), as G ranges over all graphs on m edges that contain no member of H as a subgraph. In particular, for a given graph H, we simply write f(m, H) for f(m, H) when H = {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)m(r/(r+1)) for all m. In the present article, we show that f(m, Cr-1) >= m/2 + c(r)(m(r) log(4) m)(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, H) for H = {K-2,K-s, C-5} and H = {C-4, C-5, . . . , Cr-1}, both of which improve the results of Alon et al. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.26493/1855-3974.1218.5ed | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
H-free graph,partition,maximum cut | Integer,Graph,Combinatorics,Bipartite graph,Cardinality,Partition (number theory),Maximum cut,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 1 | 1855-3966 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qinghou Zeng | 1 | 7 | 1.57 |
| liu | 2 | 195 | 21.38 |