Maximum directed cuts in digraphs with degree restriction
From MaRDI portal
Publication:3633002
DOI10.1002/JGT.20374zbMATH Open1214.05064arXiv0711.3958OpenAlexW4214844729MaRDI QIDQ3633002FDOQ3633002
Authors: Jeno Lehel, Frédéric Maffray, Myriam Preissmann 
Publication date: 16 June 2009
Published in: Journal of Graph Theory (Search for Journal in Brave)
Abstract: For integers m,k >= 1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k.
Full work available at URL: https://arxiv.org/abs/0711.3958
Recommendations
- Maximum directed cuts in acyclic digraphs
- Maximum directed cuts in graphs with degree constraints
- Covering digraphs with small indegrees or outdegrees by directed cuts
- On maximum edge cuts of connected digraphs
- Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts
Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Connectivity (05C40)
Cites Work
- Triangle-free subcubic graphs with minimum bipartite density
- Node-and edge-deletion NP-complete problems
- On incidence coloring and star arboricity of graphs
- Maximum directed cuts in acyclic digraphs
- Triangle-free partial graphs and edge covering theorems
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- MAX CUT in cubic graphs
Cited In (12)
- Max Horn SAT and the minimum cut problem in directed hypergraphs
- A note on line digraphs and the directed max-cut problem
- Maximum directed cuts in acyclic digraphs
- Online Maximum Directed Cut
- Bounds on maximum weight directed cut
- Intersection properties of maximal directed cuts in digraphs
- Covering digraphs with small indegrees or outdegrees by directed cuts
- Covering the edges of digraphs in \(\mathcal D(3,3)\) and \(\mathcal D(4,4)\) with directed cuts
- On maximum edge cuts of connected digraphs
- Oblivious algorithms for the maximum directed cut problem
- On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees
- Maximum directed cuts in graphs with degree constraints
This page was built for publication: Maximum directed cuts in digraphs with degree restriction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633002)
