List packing of graphs with bounded tree-width
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914426518503424 |
|---|---|
| author | Kashima, Masaki Maezawa, Shun-ichi Zhu, Xuding |
| author_facet | Kashima, Masaki Maezawa, Shun-ichi Zhu, Xuding |
| contents | Assume $L$ is a $k$-assignment of a graph $G$. An $L$-packing $ϕ$ of $G$ is a sequence $ϕ=(ϕ_1, \ldots, ϕ_k)$ of $k$-mappings such that each $ϕ_i$ is an $L$-coloring of $G$, and for each vertex $v$ of $G$, $\{ϕ_1(v), \ldots, ϕ_k(v)\} = L(v)$ (and hence $ϕ_i(v) \ne ϕ_j(v)$ when $i \ne j$). We say $G$ is list $k$-packable if for any $k$-assignment $L$ of $G$, there is an $L$-packing of $G$. The list packing number $χ_l^{\star}(G)$ of $G$ is the minimum integer $k$ such that $G$ is $k$-packable. For a positive integer $d$, let $t(d)$ be the maximum packing number of graphs of tree-width at most $d$. It was known that $d+1 \le t(d) \le 2d$ for any $d$. In this paper, we prove that $t(d) \le 2d-1$ for $d \ge 3$, and $t(d) \ge d+2$ for $d \ge 2$. In particular, $t(2)=4$ and $t(3)=5$. Furthermore, we show that for constant positive integers $k, d$, the problem of determining $χ_l^{\star}(G)\leq k$ or not for a graph $G$ of tree-width at most $d$ is solvable in linear time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26187 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | List packing of graphs with bounded tree-width Kashima, Masaki Maezawa, Shun-ichi Zhu, Xuding Combinatorics Assume $L$ is a $k$-assignment of a graph $G$. An $L$-packing $ϕ$ of $G$ is a sequence $ϕ=(ϕ_1, \ldots, ϕ_k)$ of $k$-mappings such that each $ϕ_i$ is an $L$-coloring of $G$, and for each vertex $v$ of $G$, $\{ϕ_1(v), \ldots, ϕ_k(v)\} = L(v)$ (and hence $ϕ_i(v) \ne ϕ_j(v)$ when $i \ne j$). We say $G$ is list $k$-packable if for any $k$-assignment $L$ of $G$, there is an $L$-packing of $G$. The list packing number $χ_l^{\star}(G)$ of $G$ is the minimum integer $k$ such that $G$ is $k$-packable. For a positive integer $d$, let $t(d)$ be the maximum packing number of graphs of tree-width at most $d$. It was known that $d+1 \le t(d) \le 2d$ for any $d$. In this paper, we prove that $t(d) \le 2d-1$ for $d \ge 3$, and $t(d) \ge d+2$ for $d \ge 2$. In particular, $t(2)=4$ and $t(3)=5$. Furthermore, we show that for constant positive integers $k, d$, the problem of determining $χ_l^{\star}(G)\leq k$ or not for a graph $G$ of tree-width at most $d$ is solvable in linear time. |
| title | List packing of graphs with bounded tree-width |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.26187 |