The nearly connected partition conjecture

At least 3 years old · documented by

Let GG be a 2-connected graph of order nn, and let n=n1+n2+⋯+nkn=n_1+n_2+\cdots+n_k be a partition of nn. A subset A⊆V(G)A\subseteq V(G) is nearly connected if it is contained in a subtree TT of GG of order at most ∣A∣+1|A|+1. The nearly connected partition conjecture. The vertex set V(G)V(G) can be partitioned into nearly connected parts A1,…,AkA_1,\ldots,A_k such that ∣Ai∣=ni|A_i|=n_i for 1≤i≤k1\leq i\leq k. The paper proves the equal-size case with all parts of size 44, while the assertion for arbitrary specified part sizes remains open.

References

Primary source

Ajit Diwan and Aniruddha Joshi, “Clique factors in powers of graphs”, arXiv:2210.17489 (2022).

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.