Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912144005529600 |
|---|---|
| author | Cambie, Stijn Hämäläinen, Rimma |
| author_facet | Cambie, Stijn Hämäläinen, Rimma |
| contents | Applications of graph colouring often involve taking restrictions into account, and it is desirable to have multiple (disjoint) solutions. In the optimal case, where there is a partition into disjoint colourings, we speak of a packing. However, even for complete bipartite graphs, the list chromatic number can be arbitrarily large, and its exact determination is generally difficult. For the packing variant, this question becomes even harder.
In this paper, we study the correspondence- and list packing numbers of (asymmetric) complete bipartite graphs. In the most asymmetric cases, Latin squares come into play. Our results show that every $z \in \mathbb Z^+ \setminus {3}$ can be equal to the correspondence packing number of a graph. Additionally, we disprove a recent conjecture that relates the list packing number and the list flexibility number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_01944 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing Cambie, Stijn Hämäläinen, Rimma Combinatorics 05C15, 05C35, 05C69, 05C70 Applications of graph colouring often involve taking restrictions into account, and it is desirable to have multiple (disjoint) solutions. In the optimal case, where there is a partition into disjoint colourings, we speak of a packing. However, even for complete bipartite graphs, the list chromatic number can be arbitrarily large, and its exact determination is generally difficult. For the packing variant, this question becomes even harder. In this paper, we study the correspondence- and list packing numbers of (asymmetric) complete bipartite graphs. In the most asymmetric cases, Latin squares come into play. Our results show that every $z \in \mathbb Z^+ \setminus {3}$ can be equal to the correspondence packing number of a graph. Additionally, we disprove a recent conjecture that relates the list packing number and the list flexibility number. |
| title | Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing |
| topic | Combinatorics 05C15, 05C35, 05C69, 05C70 |
| url | https://arxiv.org/abs/2303.01944 |