Out-degree reducing partitions of digraphs

DOI10.1016/j.tcs.2017.11.007zbMath1390.05184arXiv1707.09349OpenAlexW2740906849MaRDI QIDQ1704574

Stéphane Bessy, Frédéric Havet, Anders Yeo, Jörgen Bang-Jensen

Publication date: 12 March 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenesspolynomial algorithm2-partitionmaximum out-degree reducing partition

Mathematics Subject Classification ID

Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Majority colorings of sparse digraphs

Cites Work

• Unnamed Item
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Even cycles in directed graphs
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Permanents, Pfaffian orientations, and even directed circuits
• Majority colourings of digraphs
• Splitting digraphs
• The Even Cycle Problem for Directed Graphs
• ON THE TWO-COLOURING OF HYPERGRAPHS
• The complexity of satisfiability problems
• Digraphs

This page was built for publication: Out-degree reducing partitions of digraphs