Polynomial eta-boundedness of matching-free graphs

For each tNt\in\mathbb{N}, let MtM_t be the unique (up to isomorphism) 11-regular graph on 2t2t vertices, namely a matching of size tt. A graph is MtM_t-free if it has no induced subgraph isomorphic to MtM_t; a class is polynomially η\eta-bounded if its members satisfy η(G)ω(G)d\eta(G)\leq\omega(G)^d for some fixed positive integer dd.

Matching-free polynomial eta-boundedness conjecture. For every integer t3t\geq 3, MtM_t-free graphs are polynomially η\eta-bounded.

The source notes that even eta-boundedness is not known for M3M_3-free graphs, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Sepehr Hajebi, Yanjia Li and Sophie Spirkl, “Hitting all maximum stable sets in P_5-free graphs”, arXiv:2302.04986 (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.