Thomassen's connected partition conjecture with cross-degree condition

About 15 years old · traced to

Let kk be a positive integer. A graph is rr-connected if deleting fewer than rr vertices leaves it connected; for a vertex set M⊆V(G)M\subseteq V(G), the condition that each vertex in V1V_1 has at least kk neighbours in V2V_2 is a cross-degree condition.

Thomassen's partition conjecture. For every k∈Nk\in\mathbb{N} there exists f(k)∈Nf(k)\in\mathbb{N} such that if GG is an f(k)f(k)-connected graph and M⊆V(G)M\subseteq V(G) consists of kk vertices, then there exists a partition V1,V2V_1,V_2 of V(G)V(G) such that M⊆V1M\subseteq V_1, both G[V1]G[V_1] and G[V2]G[V_2] are kk-connected, and each vertex in V1V_1 has at least kk neighbours in V2V_2.

The source calls this a conjecture of Thomassen and explains that the graph version of the preceding tournament subdivision theorem would follow from it. Its resolution is not supplied in the paper.

References

Primary source

Jaehoon Kim, Daniela Kühn and Deryk Osthus, “Bipartitions of highly connected tournaments”, arXiv:1411.1533 (2015).

Additional references

2 papers in this index state this conjecture (2011–2014). The statement above is taken from the most recent of them; the others are arXiv:1101.2357.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.