Polynomial eta-boundedness of matching-free graphs
Polynomial eta-boundedness of matching-free graphs
For each , let be the unique (up to isomorphism) -regular graph on vertices, namely a matching of size . A graph is -free if it has no induced subgraph isomorphic to ; a class is polynomially -bounded if its members satisfy for some fixed positive integer .
Matching-free polynomial eta-boundedness conjecture. For every integer , -free graphs are polynomially -bounded.
The source notes that even eta-boundedness is not known for -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
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.