List packing of graphs with bounded tree-width

Abstract

Assume $L$ is a $k$-assignment of a graph $G$. An $L$-packing $\ddot{I}•$ of $G$ is a sequence $\ddot{I}•=(\ddot{I}{•}_1,\dots ,\ddot{I}{•}_k)$ of $k$-mappings such that each $\ddot{I}{•}_i$ is an $L$-coloring of $G$, and for each vertex $v$ of $G$, $\{\ddot{I}{•}_1(v),\dots ,\ddot{I}{•}_k(v)\}=L(v)$ (and hence $\ddot{I}{•}_i(v)\ne \ddot{I}{•}_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 $\ddot{I}{‡}_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 $\ddot{I}{‡}_l^{\star }(G)\le k$ or not for a graph $G$ of tree-width at most $d$ is solvable in linear time.