A bound on judicious bipartitions of directed graphs

DOI10.1007/S11425-017-9314-XzbMATH Open1434.05063arXiv1805.05506OpenAlexW2963794775WikidataQ128588830 ScholiaQ128588830MaRDI QIDQ2303909FDOQ2303909

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)

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$.

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

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

zbMATH Keywords

partitiondirected graphindegreeoutdegreetight 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)

Cites Work

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

Cited In (10)

• Odd induced subgraphs in planar graphs with large girth
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• On bipartitions of directed graphs with small semidegree
• Graph partitioning: an updated survey
• Bounds for judicious balanced bipartitions of graphs
• Optimal bisections of directed graphs
• On judicious bipartitions of directed graphs
• Partitioning digraphs with outdegree at least 4
• Judicious partitions of directed graphs
• Title not available (Why is that?)

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)