Query：
学者姓名：曾庆厚
Refining：
Year
Type
Indexed by
Source
Complex
Former Name
Co-
Language
Clean All
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.
Keyword ：
H-free graph H-free graph maximum cut maximum cut partition partition
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zeng, Qinghou , Hou, Jianfeng . Maximum cuts of graphs with forbidden cycles [J]. | ARS MATHEMATICA CONTEMPORANEA , 2018 , 15 (1) : 147-160 . |
| MLA | Zeng, Qinghou 等. "Maximum cuts of graphs with forbidden cycles" . | ARS MATHEMATICA CONTEMPORANEA 15 . 1 (2018) : 147-160 . |
| APA | Zeng, Qinghou , Hou, Jianfeng . Maximum cuts of graphs with forbidden cycles . | ARS MATHEMATICA CONTEMPORANEA , 2018 , 15 (1) , 147-160 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Let r >= 3 and k >= 2 be fixed integers. Bollobas and Scott conjectured that every r-uniform hypergraph with m edges has a vertex partition into k sets with at most m/k(r)+o(m) edges in each set, and proved the conjecture in the case r = 3. In this paper, we confirm this conjecture in the case r = 4 by showing that every 4-uniform hypergraph with m edges has a vertex partition into k sets with at most m/k(4) + O(m(8/9)) edges in each set.
Keyword ：
Azuma-Hoeffding inequality Azuma-Hoeffding inequality hypergraph hypergraph partition partition
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Hou, Jianfeng , Wu, Shufei , Zeng, Qinghou et al. THE BOLLOBAS SCOTT CONJECTURE FOR 4-UNIFORM HYPERGRAPHS [J]. | SIAM JOURNAL ON DISCRETE MATHEMATICS , 2018 , 32 (1) : 505-521 . |
| MLA | Hou, Jianfeng et al. "THE BOLLOBAS SCOTT CONJECTURE FOR 4-UNIFORM HYPERGRAPHS" . | SIAM JOURNAL ON DISCRETE MATHEMATICS 32 . 1 (2018) : 505-521 . |
| APA | Hou, Jianfeng , Wu, Shufei , Zeng, Qinghou , Zhu, Wenxing . THE BOLLOBAS SCOTT CONJECTURE FOR 4-UNIFORM HYPERGRAPHS . | SIAM JOURNAL ON DISCRETE MATHEMATICS , 2018 , 32 (1) , 505-521 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
For a graph G, let f (G) denote the maximum number of edges in a bipartite subgraph of G. For an integer m and for a fixed graph H, let f (m, H) denote the minimum possible cardinality of f (G) as G ranges over all graphs on m edges that contain no copy of H. We give a general lower bound for f (m, H) which extends a result of Erdos and Lovasz and we study this function for any bipartite graph H with maximum degree at most t >= 2 on one side.
Keyword ：
bipartite subgraph bipartite subgraph H-free graph H-free graph partition partition
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zeng, Qinghou , Hou, Jianfeng . BIPARTITE SUBGRAPHS OF H-FREE GRAPHS [J]. | BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY , 2017 , 96 (1) : 1-13 . |
| MLA | Zeng, Qinghou et al. "BIPARTITE SUBGRAPHS OF H-FREE GRAPHS" . | BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY 96 . 1 (2017) : 1-13 . |
| APA | Zeng, Qinghou , Hou, Jianfeng . BIPARTITE SUBGRAPHS OF H-FREE GRAPHS . | BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY , 2017 , 96 (1) , 1-13 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
For positive integers k >= 2 and m, let g(k) (m) be the smallest integer such that for each graph G with m edges there exists a k-partition V (G) = V-1 boolean OR . . . boolean OR V-k in which each V-i contains at most g(k) (m) edges. Bollobas and Scott showed that g(k) (m) <= m/k(2) + k-1/2k(2) (root 2m + root 1/4 - 1/2). Ma and Yu posed the following problem: is it true that the limsup of m/k(2) + k-1/2k(2) root 2m - g(k) (m) tends to infinity asmtends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobas and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k-cut has a k-partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobas and Scott. (C) 2016 Wiley Periodicals, Inc.
Keyword ：
graph graph judicious partition judicious partition max-cut max-cut
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Hou, Jianfeng , Zeng, Qinghou . On a Problem of Judicious k-Partitions of Graphs [J]. | JOURNAL OF GRAPH THEORY , 2017 , 85 (3) : 619-643 . |
| MLA | Hou, Jianfeng et al. "On a Problem of Judicious k-Partitions of Graphs" . | JOURNAL OF GRAPH THEORY 85 . 3 (2017) : 619-643 . |
| APA | Hou, Jianfeng , Zeng, Qinghou . On a Problem of Judicious k-Partitions of Graphs . | JOURNAL OF GRAPH THEORY , 2017 , 85 (3) , 619-643 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Let G = (V,E) be a graph with m edges. For reals p is an element of [0, 1] and q = 1 - p, let m(p)(G) be the minimum of qe(V-1) + pe(V-2) over partitions V = V (1) boolean OR V-2, where e(V-i) denotes the number of edges spanned by V-i. We show that if m(p)(G) = pqm - delta, then there exists a bipartition V-1, V-2 of G such that e(V-1) <= p(2) m - delta + p root m/2 + o(root m) and e(V-2) <= q(2) m - delta + q root m/2 + o(root m) for delta = o (m(2/3)). This is sharp for complete graphs up to the error term o(root m). For an integer k >= 2, let f(k)(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if f(k)(G) = (1 - 1/k) m + alpha, then G admits a k-partition such that each vertex class spans at most m/k(2) - ohm(m/k(7.5)) edges for alpha = ohm(m/k(6)). Both of the above improve the results of Bollob ' as and Scott.
Keyword ：
biased partition biased partition Graph Graph judicious partition judicious partition Max-Cut Max-Cut
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zeng, Qing Hou , Hou, Jian Feng , Deng, Jin et al. Biased Partitions and Judicious k-Partitions of Graphs [J]. | ACTA MATHEMATICA SINICA-ENGLISH SERIES , 2017 , 33 (5) : 668-680 . |
| MLA | Zeng, Qing Hou et al. "Biased Partitions and Judicious k-Partitions of Graphs" . | ACTA MATHEMATICA SINICA-ENGLISH SERIES 33 . 5 (2017) : 668-680 . |
| APA | Zeng, Qing Hou , Hou, Jian Feng , Deng, Jin , Lei, Xia . Biased Partitions and Judicious k-Partitions of Graphs . | ACTA MATHEMATICA SINICA-ENGLISH SERIES , 2017 , 33 (5) , 668-680 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. Let k >= 2 be an integer and let G be a hypergraph with m(i) edges of size i for i = 1, 2. Bollobas and Scott conjectured that G has a partition into k classes, each of which contains at most m(1)/k + m(2)/k(2) + O(root m(1) + m(2)) edges. In this paper, we confirm the conjecture affirmatively by showing that G has a partition into k classes, each of which contains at most m(1)/k + m(2)/k(2) + k - 1/2k(2) root 2(km(1) + m(2)) + O(1) edges. This bound is tight up to O(1).
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Hou, Jianfeng , Zeng, Qinghou . Judicious Partitioning of Hypergraphs with Edges of Size at Most 2 [J]. | COMBINATORICS PROBABILITY & COMPUTING , 2017 , 26 (2) : 267-284 . |
| MLA | Hou, Jianfeng et al. "Judicious Partitioning of Hypergraphs with Edges of Size at Most 2" . | COMBINATORICS PROBABILITY & COMPUTING 26 . 2 (2017) : 267-284 . |
| APA | Hou, Jianfeng , Zeng, Qinghou . Judicious Partitioning of Hypergraphs with Edges of Size at Most 2 . | COMBINATORICS PROBABILITY & COMPUTING , 2017 , 26 (2) , 267-284 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Let G be a weighted hypergraph with edges of size at most 2. Bollobas and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w (1)-Delta(1))/2+2w (2)/3, where wi is the total weight of edges of size i and Delta(1) is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w (0)-1)/6+(w (1)-Delta(1))/3+2w (2)/3, where w (0) is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K (2) and K (1,3), admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobas and Scott.
Keyword ：
graph graph judicious partition judicious partition partition partition weighted hypergraph weighted hypergraph
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zeng, Qinghou , Hou, Jianfeng . Bounds for the number of meeting edges in graph partitioning [J]. | CZECHOSLOVAK MATHEMATICAL JOURNAL , 2017 , 67 (3) : 741-752 . |
| MLA | Zeng, Qinghou et al. "Bounds for the number of meeting edges in graph partitioning" . | CZECHOSLOVAK MATHEMATICAL JOURNAL 67 . 3 (2017) : 741-752 . |
| APA | Zeng, Qinghou , Hou, Jianfeng . Bounds for the number of meeting edges in graph partitioning . | CZECHOSLOVAK MATHEMATICAL JOURNAL , 2017 , 67 (3) , 741-752 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let k be a positive integer and G a graph with in edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V-1, ... V-k such that e(V-i) <= m/k(2) + k-1/2k(2) (root 2m + 1/4 - 1/2) + 2/3 for each i is an element of {1, 2, ..., k} and e(V-1, ..., V-k) >= k-1/km + k-1/2k (root 2m + 1/4 - 1/2) - (k-2)(2)/8k, congruent to where e(V-i) is the number of edges with both ends in V-i and e (V-1, ..., V-k) = m - Sigma(k)(i=1) e(V-i). This partially solves a problem proposed by Bollobas and Scott, and, for some values of m, solves the problem affirmatively. (C) 2014 Elsevier B.V. All rights reserved.
Keyword ：
Graph Graph Judicious partition Judicious partition Max-Cut problem Max-Cut problem Switching Switching
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Fan, Genghua , Hou, Jianfeng , Zeng, Qinghou . A bound for judicious k-partitions of graphs [J]. | DISCRETE APPLIED MATHEMATICS , 2014 , 179 : 86-99 . |
| MLA | Fan, Genghua et al. "A bound for judicious k-partitions of graphs" . | DISCRETE APPLIED MATHEMATICS 179 (2014) : 86-99 . |
| APA | Fan, Genghua , Hou, Jianfeng , Zeng, Qinghou . A bound for judicious k-partitions of graphs . | DISCRETE APPLIED MATHEMATICS , 2014 , 179 , 86-99 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
