Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties

Generalizing well-known results of Erdős and Lovász, we show that every graph (Formula presented.) contains a spanning (Formula presented.) -partite subgraph (Formula presented.) with (Formula presented.), where (Formula presented.) is the edge-connectivity of (Formula presented.). In particular, together with a well-known result due to Nash-Williams and Tutte, this implies that every 7-edge-connected graph contains a spanning bipartite graph whose edge set decomposes into two edge-disjoint spanning trees. We show that this is best possible as it does not hold for infinitely many 6-edge-connected graphs. For directed graphs, it was shown by Bang-Jensen et al. that there is no (Formula presented.) such that every (Formula presented.) -arc-connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3-partite subdigraph and that every strong semicomplete digraph on at least six vertices contains a spanning strong bipartite subdigraph. We generalize this result to higher connectivities by proving that, for every positive integer (Formula presented.), every (Formula presented.) -arc-connected digraph contains a spanning ((Formula presented.))-partite subdigraph which is (Formula presented.) -arc-connected and this is best possible. A conjecture by Kreutzer et al. implies that every digraph of minimum out-degree (Formula presented.) contains a spanning 3-partite subdigraph with minimum out-degree at least (Formula presented.). We prove that the bound (Formula presented.) would be best possible by providing an infinite class of digraphs with minimum out-degree (Formula presented.) which do not contain any spanning 3-partite subdigraph in which all out-degrees are at least (Formula presented.). We also prove that every digraph of minimum semidegree at least (Formula presented.) contains a spanning 6-partite subdigraph in which every vertex has in- and out-degree at least (Formula presented.).