Hajebi–Li–Spirkl conjecture for graphs without large induced matchings
Hajebi–Li–Spirkl conjecture for graphs without large induced matchings
For a graph , let be the smallest size of a subset of intersecting every maximum independent set, and let denote its clique number. An induced matching of size consists of vertices whose only edges among them are for . Hajebi–Li–Spirkl conjecture. If has no induced matching of size , then
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 , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.