arXiv Open Access 2025

The unavoidable drawings of complete multipartite graphs

Jozsef Balogh Irene Parada Gelasio Salazar

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

math.CO

Penulis (3)

Jozsef Balogh

Irene Parada

Gelasio Salazar

Format Sitasi

APA MLA BibTeX

Balogh, J., Parada, I., Salazar, G. (2025). The unavoidable drawings of complete multipartite graphs. https://arxiv.org/abs/2509.20625

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓