Sharpness conjecture for forbidden induced subgraphs and JEP decidability

Let HH be a graph, let SS be a finite set of graphs, and write Forb(S)\operatorname{Forb}_\subseteq(S) for the graphs containing no member of SS as an induced subgraph. One-forbidden-graph sharpness conjecture. Problem JEP is decidable for all finite sets SS containing HH if and only if HP4H\subseteq P_4. The paper proves the if direction; moreover, HP4H\subseteq P_4 is equivalent to Forb(H)\operatorname{Forb}_\subseteq(H) being well-quasi-ordered under induced subgraph containment. The converse direction remains conjectural.

Sources & referencesView supporting material

Primary source

Daniel Carter, “On the joint embedding property for cographs and trees”, arXiv:2409.06127 (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.