Maximum Cuts in $$\mathscr {H}$$ H -Free Graphs
- PDF / 328,838 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 167 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Maximum Cuts in H-Free Graphs Huawen Ma1,2 Received: 8 June 2019 / Revised: 17 April 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract For a graph G, let f(G) be the maximum number of edges in a cut of G. For a positive integer m and a set of graphs H, let f ðm; HÞ be the minimum possible cardinality of f(G), as G ranges over all graphs on m edges which contain no graphs in H. Suppose that r 8 is an even integer and H ¼ fC5 ; C6 ; . . .; Cr1 g. In this r paper, we prove that f ðm; HÞ m=2 þ cmrþ1 for some real c [ 0, which improves a result of Alon et al. We also give a general lower bound on f ðm; HÞ when H ¼ fKs þ Kt g. This extends a result of Zeng and Hou. Keywords Maximum cut Partition H-free graph
1 Introduction One of the classical partition problems is the well-known Max-Cut problem: Given a graph G, find a bipartite subgraph H of G maximizing the number of edges in H. It is NP-hard even when restricted to triangle-free cubic graphs [20], and has been a very active research subject in both combinatorics and computer science [4, 5, 10, 13, 14, 18, 19]. For a graph G, let f(G) denote the maximum number of edges in a bipartite subgraph of G. For an integer m, let f(m) denote the minimum value of f(G), as G ranges over all graphs with m edges. That is, f(m) is the largest integer f such that any graph with m edges contains a bipartite subgraph with at least f edges. In 1973, answering a question of Erd}os, Edwards [6, 7] proved that for each m, This work is supported by YDBK (No. 2019-71). & Huawen Ma [email protected] 1
Colledge of Mathematics and Computer Science, Yan’an University, Shanxi 716000, China
2
Center for Discrete Mathematics, Fuzhou University, Fujian 350003, China
123
Graphs and Combinatorics
m 1 f ðmÞ þ 2 4
! rffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 1 1 2m þ : 4 2
Note that the bound is tight as evidenced by complete graphs of odd order. Suppose that H is a set 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; fHgÞ. Determining f(m, H) is one of the core issues of graph partition problems. Erd}os [8] firstly studied the Max-Cut of triangle-free graphs and proved that f ðm; K3 Þ m=2 þ cm2=3 for some positive constant c. After a series of papers by various researchers [15, 16], Alon [1] proved that f ðm; K3 Þ ¼ m=2 þ Hðm4=5 Þ for all m. Alon ET AL. [2] extended this to graphs with girth (the length of the shortest cycle) at least r and proved that m r f ðm; fC3 ; C4 ; . . .; Cr1 gÞ þ cmrþ1 2 for some real c [ 0. Our first result extends this by showing: Theorem 1 Let r 8 be a fixed even integer and H ¼ fC5 ; C6 ; . . .; Cr1 g. Then there exists cðrÞ [ 0 such that m r f ðm; HÞ þ cðrÞmrþ1 2 for each positive integer m. For a fixed graph H, Alon et al. [2] conjectured that there exists a positive constant ¼ ðHÞ such that f ðm; HÞ m=2 þ Xðm3=4þ
Data Loading...
