The nearly connected partition conjecture

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 AV(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 1ik1\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.

Sources & referencesView supporting material

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.