Maximum directed cuts in graphs with degree constraints

DOI10.1007/s00373-011-1056-8zbMath1256.05122OpenAlexW2066592985MaRDI QIDQ1926032

Xingxing Yu, Bao-Gang Xu

Publication date: 27 December 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1056-8

zbMATH Keywords

triangle-free graphNP-hard problemsubcubic graphacyclic digraphmax cut problemHall ratiodirected cutmaximum directed cutdigraphs containing no directed trianglesmaximum dicut

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Intersection properties of maximal directed cuts in digraphs ⋮ On Maximum Edge Cuts of Connected Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Triangle-free subcubic graphs with minimum bipartite density
• Hall ratio of the Mycielski graphs
• Bipartite subgraphs
• Improved approximation of Max-Cut on graphs of bounded degree
• MAX CUT in cubic graphs
• Maximum directed cuts in acyclic digraphs
• Maximum directed cuts in digraphs with degree restriction
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Node-and edge-deletion NP-complete problems
• Some Extremal Properties of Bipartite Subgraphs
• Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs

This page was built for publication: Maximum directed cuts in graphs with degree constraints