Hajebi–Li–Spirkl conjecture for graphs without large induced matchings

For a graph GG, let h(G)h(G) be the smallest size of a subset of V(G)V(G) intersecting every maximum independent set, and let ω(G)\omega(G) denote its clique number. An induced matching of size tt consists of vertices {ai,bi}i[t]\{a_i,b_i\}_{i\in [t]} whose only edges among them are aibia_ib_i for i[t]i\in[t]. Hajebi–Li–Spirkl conjecture. If GG has no induced matching of size tt, then

h(G)ω(G)Ot(1).h(G)\leq \omega(G)^{O_t(1)}.

This conjecture asks for a polynomial bound on the size of a set piercing every maximum independent set in graphs excluding a fixed induced matching; the paper proves the stronger bound h(G)ω(G)3t3+o(1)h(G)\leq \omega(G)^{3t-3+o(1)}, thereby resolving it.

Sources & referencesView supporting material

Primary source

Jiangdong Ai, Hong Liu, Zixiang Xu and Qiang Zhou, “Piercing independent sets in graphs without large induced matching”, arXiv:2403.19737 (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.