On asymptotic packing of convex geometric and ordered graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910342235291648 |
|---|---|
| author | Nie, Jiaxi Surya, Erlang Zeng, Ji |
| author_facet | Nie, Jiaxi Surya, Erlang Zeng, Ji |
| contents | A convex geometric graph $G$ is said to be packable if there exist edge-disjoint copies of $G$ in the complete convex geometric graph $K_n$ covering all but $o(n^2)$ edges. We prove that every convex geometric graph with cyclic chromatic number at most $4$ is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most $3$ is packable. Arguments based on the average length of edges imply these results are best possible. We also identify a class of convex geometric graphs that are packable due to having many "long" edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_11624 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On asymptotic packing of convex geometric and ordered graphs Nie, Jiaxi Surya, Erlang Zeng, Ji Combinatorics 05B40, 05C35, 05D40 A convex geometric graph $G$ is said to be packable if there exist edge-disjoint copies of $G$ in the complete convex geometric graph $K_n$ covering all but $o(n^2)$ edges. We prove that every convex geometric graph with cyclic chromatic number at most $4$ is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most $3$ is packable. Arguments based on the average length of edges imply these results are best possible. We also identify a class of convex geometric graphs that are packable due to having many "long" edges. |
| title | On asymptotic packing of convex geometric and ordered graphs |
| topic | Combinatorics 05B40, 05C35, 05D40 |
| url | https://arxiv.org/abs/2207.11624 |