Gyárfás–Sumner analogue for eta-boundedness

For finite graphs GG and HH, say that GG is HH-free if it has no induced subgraph isomorphic to HH. Write ω(G)\omega(G) for the clique number and η(G)\eta(G) for the minimum size of a set meeting every maximum stable set. A graph class is η\eta-bounded if its members satisfy an upper bound on η\eta depending only on clique number.

Gyárfás–Sumner analogue for η\eta-boundedness. For every forest HH, there exists a function f:NNf:\mathbb{N}\to\mathbb{N} such that every HH-free graph GG satisfies η(G)f(ω(G))\eta(G)\leq f(\omega(G)).

The conjecture is motivated by the Gyárfás–Sumner conjecture and is known for stars and induced subgraphs of P4P_4, but remains open in general.

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.