List and total colorings of multiset permutation graphs

Abstract

Let $k$ and $\ell$ be positive integers. The multiset star transposition graph ST${}_k^{\ell }$ has as vertices the $k\ell$-strings $v_0\cdots v_{k\ell -1}$ on $k$ symbols, each symbol repeated $\ell$ times, and edges given by the transpositions $(v_0{v}_i)$ with $v_i\ne v_0$ ($0<i<k\ell$). It is shown for $k>1$ and $\ell >2$ that ST${}_k^{\ell }$ is $(\ell -1)$-choosable and that, as a result, admits total colorings. In order to prove such assertions, the notion of efficient domination set (or E-set) of a graph is generalized for $\ell >1$ to that of an efficient dominating${}^{\ell }$-set and applied to the graphs ST${}_k^{\ell }$\,, showing they admit vertex partitions that generalize the Dejter-Serra partitions of ST${}_k^1$ into E-sets, but not efficiently in the sense that the distance of each E${}^{\ell }$-set be 3. Efficiently in such sense however, $S{T}_k^2$ and the related 2-set pancake permutation graph PC${}_k^2$, among other intermediate permutation graphs, are shown to admit total colorings with $2k-1$ colors that determine partitions into $2k-1$ E-sets, each with distance 3. Furthermore, associated E-chains are examined.

16 pages, 4 figures. arXiv admin note: text overlap with arXiv:2007.09736