Sharpness conjecture for forbidden induced subgraphs and JEP decidability
Sharpness conjecture for forbidden induced subgraphs and JEP decidability
Let be a graph, let be a finite set of graphs, and write for the graphs containing no member of as an induced subgraph. One-forbidden-graph sharpness conjecture. Problem JEP is decidable for all finite sets containing if and only if . The paper proves the if direction; moreover, is equivalent to 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
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.