Talk:Head-disjoint strongly connected orientations

Finding an induced cubic subgraph -- Tamás Király (talk) 21:54, 3 October 2015 (UTC)

The result of Mészáros that (2,1)-partition-connectivity of the corresponding bipartite graph is sufficient depends on the following consequence of Olson's theorem: If a bipartite graph has at least 2n-1 edges and in one of the colour classes every node has degree 3, then it contains an induced subgraph where every degree is divisible by 3. Can we give a polynomial-time algorithm to find such a subgraph? Maybe the simplest case is when every degree in the other class is 6, except for one that is 5. Is it true that there always exists a cubic induced subgraph? In general, finding an induced cubic subgraph in bipartite graphs is NP-complete (see [1]), but this special case may be tractable.