# 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

## 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 language English Journal of Graph Theory 92 2 130-151 0364-9024 https://doi.org/10.1002/jgt.22444 Published - 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.