The isolation-number lower-bound conjectures

For a graph GG, let iso(G,k){\rm iso}(G,k) be the maximum number of pairwise disjoint kk-clique isolating sets in a partition of V(G)V(G), and let isoc(G){\rm iso}_c(G) be the analogous number for cycle isolating sets. The isolation-number lower-bound conjectures. (i) If k3k \geq 3 and GG is connected with GKkG \ncong K_k, then

iso(G,k)k+1.{\rm iso}(G,k) \geq k+1.

(ii) If GG is connected with GC3G \ncong C_3, then

isoc(G)4.{\rm iso}_c(G) \geq 4.

These are explicitly stated to be equivalent to the two partition conjectures above, so they do not constitute additional independent claims.

Sources & referencesView supporting material

Primary source

Gang Zhang, Weiling Yang and Xian'an Jin, “Isolation partitions in graphs”, arXiv:2411.03666 (2024).

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.