On the joint embedding property for cographs and trees
<|reference_start|>On the joint embedding property for cographs and trees: A family of graphs $\mathcal{F}$ is said to have the joint embedding property (JEP) if for every $G_1, G_2\in \mathcal{F}$, there is an $H\in \mathcal{F}$ that contains both $G_1$ and $G_2$ as induced subgraphs. If $\mathcal{F}$ is given by a finite set $S$ of forbidden induced subgraphs, it is known that determining if $\mathcal{F}$ has JEP is undecidable. We prove that this problem is decidable if $P_4\in S$ and generalize this result to families of rooted labeled trees under topological containment, bounded treewidth families under the graph minor relation, and bounded cliquewidth families under the induced subgraph relation.<|reference_end|>
@article{carter2024on,
    title={On the joint embedding property for cographs and trees},
    author={Daniel Carter},
    journal={arXiv preprint arXiv:2409.06127},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.06127},
    primaryClass={math.CO cs.DM cs.DS}
}