The unavoidable drawings of complete multipartite graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908558094761984 |
|---|---|
| author | Balogh, Jozsef Parada, Irene Salazar, Gelasio |
| author_facet | Balogh, Jozsef Parada, Irene Salazar, Gelasio |
| contents | In a simple drawing of a graph every pair of edges intersect each other in at most one point, which is either a common endvertex or a proper crossing. For each positive integer $n$, Negami identified a drawing $B_n$ of the complete bipartite graph $K_{n,n}$, and proved that if $N$ is sufficiently large, then every drawing of $K_{N,N}$ contains a drawing of $K_{n,n}$ weakly isomorphic to $B_n$. Thus $B_n$ is (up to weak isomorphism) the only {\em unavoidable} drawing of $K_{n,n}$. We extend this result to complete multipartite graphs, characterizing their unavoidable drawings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20625 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The unavoidable drawings of complete multipartite graphs Balogh, Jozsef Parada, Irene Salazar, Gelasio Combinatorics 05C10, 68R10 In a simple drawing of a graph every pair of edges intersect each other in at most one point, which is either a common endvertex or a proper crossing. For each positive integer $n$, Negami identified a drawing $B_n$ of the complete bipartite graph $K_{n,n}$, and proved that if $N$ is sufficiently large, then every drawing of $K_{N,N}$ contains a drawing of $K_{n,n}$ weakly isomorphic to $B_n$. Thus $B_n$ is (up to weak isomorphism) the only {\em unavoidable} drawing of $K_{n,n}$. We extend this result to complete multipartite graphs, characterizing their unavoidable drawings. |
| title | The unavoidable drawings of complete multipartite graphs |
| topic | Combinatorics 05C10, 68R10 |
| url | https://arxiv.org/abs/2509.20625 |