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

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-09965

Browse the full library · About the Tower of Babel