Sharpness conjecture for forbidden induced subgraphs and JEP decidability

About 2 years old · traced to

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 H⊆P4H\subseteq P_4. The paper proves the if direction; moreover, H⊆P4H\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.

References

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.