Bisecting a 4-connected graph with three resource sets (Q997070): Difference between revisions

Let \(G=(V,E)\) be an undirected graph and let \(T_1,T_2,\ldots,T_k\) be pairwise disjoint subsets of \(V\) such that \(| T_i| \) is even, for \(i=1,2,\ldots,k\). A partition of \(V\) into two subsets \(V_1\) and \(V_2\) such that the graphs induced in \(G\) by \(V_1\) and \(V_2\) are connected and \(| V_1\cap T_i| =| V_2\cap T_i| =\frac{| T_i| }{2}\), for \(i=1,2,\ldots,k\), is called a \(k\)-bisection of \(G\). It is known that every \((k+1)\)-connected graph admits a \(k\)-bisection for \(k=1,2\) and it was conjectured that every \((k+1)\)-connected graph admits a \(k\)-bisection for \(k\geq 3\) as well. The authors disprove this conjecture for \(k=3\) but show that a \(4\)-connected graph \(G\) admits a \(3\)-bisection if we additionally assume that \(G\) contains a copy of \(K_4\) as its subgraph. Moreover, they give an algorithm constructing such a \(3\)-bisection working in time \(O(| V| ^3\text{log} | V| )\). They also show that for an arc version of the problem \((k+1)\)-edge connectivity suffices for \(k=1,2,3\).