Lower Bound for Independence Covering in C ₄ -Free Graphs

An independent set in a graph G is a set S of pairwise non-adjacent vertices in G . A family \(F\) of independent sets in G is called a k - independence covering family if for every independent set I in G of size at most k , there exists an \(S ∈ F\) such that \(I ⊆ S\) . Lokshtanov et al. (ACM Transactions on Algorithms , 2020) showed that graphs of degeneracy d admit k -independence covering families of size \({k(d+1)}{k} · 2ᵒ⁽ᵏᵈ⁾ · log n\) and used this result to design efficient parameterized algorithms for a number of problems, including Stable Odd Cycle Transversal and Stable Multicut . In light of the results of Lokshtanov et al. (ACM Transactions on Algorithms, 2020) it is quite natural to ask whether even more general families of graphs admit k -independence covering families of size \(f(k)nO(1)\) . Graphs that exclude a complete bipartite graph \(Kd+1,d+1\) with \(d+1\) vertices on both sides as a subgraph, called \(Kd+1,d+1\) - free graphs , are a frequently considered generalization of d -degenerate graphs. This motivates the question of whether \(Kd,d\) -free graphs admit k -independence covering families of size \(f(k,d)nO(1)\) . Our main result is a resounding “no” to this question—specifically, we prove that even \(K2,2\) -free graphs (or equivalently \(C_4\) -free graphs) do not admit k -independence covering families of size \(f(k)nk/4-ε\) .