The generalized kk-independence lower-bound conjecture

Let k2k\geq 2 be an integer, and let RiR_i be the sequence of trees of order kiki defined by taking R1R_1 to be a kk-tree and, for i2i\geq 2, obtaining RiR_i by adding an edge joining a vertex of a member of Ri1R_{i-1} to a vertex of a kk-tree. For a simple graph GG, let αk(G)\alpha_k(G) denote its generalized kk-independence number, let n=V(G)n=|V(G)|, let ω(G)\omega(G) be the dimension of its cycle space, and let ΓG\Gamma_G be the graph whose components occur in the claimed characterization.

Generalized kk-independence conjecture. For every nn-vertex simple graph GG,

αk(G)k1k[nω(G)].\alpha_k(G)\geq \frac{k-1}{k}[n-\omega(G)].

Equality holds if and only if all the following conditions hold: the cycles of GG, if any, are pairwise vertex-disjoint; every cycle of GG, if any, has order congruent to 11 modulo kk; and each component TT of ΓG\Gamma_G satisfies VT0(modk)|V_T|\equiv 0\pmod{k} and belongs to RVT/kR_{|V_T|/k}. This conjecture extends the paper's proved sharp bound for k=4k=4 to general integers k2k\geq 2; the proposed equality characterization depends on the recursively defined trees RiR_i.

Sources & referencesView supporting material

Primary source

Jing Huang, “A sharp lower bound on the generalized 4-independence number”, arXiv:2509.09925 (2025).

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.