A bound on judicious bipartitions of directed graphs

DOI10.1007/S11425-017-9314-XMaRDI QIDQ2303909zbMATH OpenOpenAlexWikidataFDO

Authors Xingxing Yu, Xia Zhang, Jianfeng Hou, Hua Wen Ma

Publication date 6 March 2020

Published in Science China. Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.05506

zbMATH Keywords

directed graphindegreeoutdegreepartitiontight component

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously, which have received a lot of attentions lately. Scott asked the following natural question: What is the maximum constant $c_d$ such that every directed graph $D$ with $m$ arcs and minimum outdegree $d$ admits a bipartition $V(D)=V_{1}cup{V}_2$ satisfying $mine(V_1,V_2),e(V_2,V_1)ge{c}_{d}m$? Here, for $i=1,2$, $e(V_i,V_{3-i})$ denotes the number of arcs in $D$ from $V_i$ to $V_{3-i}$. Lee, Loh, and Sudakov %[Judicious partitions of directed graphs, Random Struct. Alg. 48 %(2016) 147--170] conjectured that every directed graph $D$ with $m$ arcs and minimum outdegree at least $dge2$ admits a bipartition $V(D)=V_{1}cup{V}_2$ such that [ min{e(V_1,V_2),e(V_2,V_1)}geq Big(frac{d-1}{2(2d-1)}+ o(1)Big)m. ] %While it is not known whether or not the minimum outdegree condition %alone is sufficient, w We show that this conjecture holds under the additional natural condition that the minimum indegree is also at least $d$.

Recommendations

• On judicious bipartitions of directed graphs
• Judicious partitions of directed graphs
• Partitioning digraphs with outdegree at least 4
• On judicious bipartitions of graphs
• Bipartitions of oriented graphs

Cites work

• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Bipartite density of triangle-free subcubic graphs
• Bipartite subgraphs
• Bipartition of graph under degree constraints
• Bipartitions of oriented graphs
• Bisections of graphs
• Bisections of graphs without short cycles
• Bounds for pairs in judicious partitioning of graphs
• scientific article; zbMATH DE number 3510345 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Judicious partitions and related problems
• Judicious partitions of directed graphs
• Judicious partitions of hypergraphs
• Maximum directed cuts in acyclic digraphs
• Node-and edge-deletion NP-complete problems
• On bisections of directed graphs
• On judicious partitions of uniform hypergraphs
• On maximum edge cuts of connected digraphs
• On several partitioning problems of Bollobás and Scott
• On tight components and anti-tight components
• Probability Inequalities for Sums of Bounded Random Variables
• Problems and results on judicious partitions
• Some Extremal Properties of Bipartite Subgraphs
• The Bollobás-Scott conjecture for 4-uniform hypergraphs
• Triangle-free subcubic graphs with minimum bipartite density
• Weighted sums of certain dependent random variables

Cited in

(10)

• Bounds for judicious balanced bipartitions of graphs
• On bipartitions of directed graphs with small semidegree
• On judicious bipartitions of directed graphs
• Odd induced subgraphs in planar graphs with large girth
• Judicious partitions of directed graphs
• scientific article; zbMATH DE number 6311292 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Partitioning digraphs with outdegree at least 4
• Graph partitioning: an updated survey
• Optimal bisections of directed graphs

This page was built for publication: A bound on judicious bipartitions of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2303909)