List and total colorings of multiset permutation graphs
2026
Read List and total colorings of multiset permutation graphs (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-09965.txt.
Description
Graphs built from permuting multiset strings offer a test bed for coloring questions. A 2026 paper by Italo J. Dejter studies the multiset star transposition graph, whose vertices are strings with each symbol repeated a fixed number of times, joined by swaps with the first position. The question is when such graphs admit list and total colorings.
Dejter shows the graphs are choosable under stated conditions and therefore admit total colorings. The proof generalizes efficient dominating sets to a multiset version and builds vertex partitions extending earlier work. For a special case, the graphs admit total colorings with a matching count of colors, each color class an efficient dominating set at distance three.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-09965