Bipartite spanning sub(di)graphs induced by 2-partitions

J. Bang-Jensen, S. Bessy, F. Havet*, A. Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

101 Downloads (Pure)

Abstract

For a given (Formula presented.) -partition (Formula presented.) of the vertices of a (di)graph (Formula presented.), we study properties of the spanning bipartite subdigraph (Formula presented.) of (Formula presented.) induced by those arcs/edges that have one end in each (Formula presented.). We determine, for all pairs of nonnegative integers (Formula presented.), the complexity of deciding whether (Formula presented.) has a 2-partition (Formula presented.) such that each vertex in (Formula presented.) (for (Formula presented.)) has at least (Formula presented.) (out-)neighbours in (Formula presented.). We prove that it is (Formula presented.) -complete to decide whether a digraph (Formula presented.) has a 2-partition (Formula presented.) such that each vertex in (Formula presented.) has an out-neighbour in (Formula presented.) and each vertex in (Formula presented.) has an in-neighbour in (Formula presented.). The problem becomes polynomially solvable if we require (Formula presented.) to be strongly connected. We give a characterisation of the structure of (Formula presented.) -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes (Formula presented.) -complete even for strong digraphs. A further result is that it is (Formula presented.) -complete to decide whether a given digraph (Formula presented.) has a (Formula presented.) -partition (Formula presented.) such that (Formula presented.) is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.

Original languageEnglish
JournalJournal of Graph Theory
Volume92
Issue number2
Pages (from-to)130-151
ISSN0364-9024
DOIs
Publication statusPublished - Oct 2019

Keywords

  • 2-partition, spanning bipartite subdigraph
  • eulerian
  • minimum out-degree
  • strong spanning subdigraph

Fingerprint

Dive into the research topics of 'Bipartite spanning sub(di)graphs induced by 2-partitions'. Together they form a unique fingerprint.

Cite this