On the joint embedding property for cographs and trees
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929493891874816 |
|---|---|
| author | Carter, Daniel |
| author_facet | Carter, Daniel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06127 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the joint embedding property for cographs and trees Carter, Daniel Combinatorics Discrete Mathematics Data Structures and Algorithms 05C85 (Primary) 05C05, 68Q45 (Secondary) 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. |
| title | On the joint embedding property for cographs and trees |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C85 (Primary) 05C05, 68Q45 (Secondary) |
| url | https://arxiv.org/abs/2409.06127 |