On Sierpiński packing chromatic number and recognition of Sierpiński products

Přemysl Holub, Sandi Klavžar · 2025

Read On Sierpiński packing chromatic number and recognition of Sierpiński products by Přemysl Holub, Sandi Klavžar (2025) 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-2507-06730.txt.

Description

Přemysl Holub and Sandi Klavžar study colorings of a special graph construction in which copies of one graph are joined according to a rule set by another. They define two new numbers for such products: the smallest packing coloring count that any joining rule allows, and the largest. A packing coloring assigns numbers so that vertices sharing a number sit far apart, with the required distance growing with the number.

The pair settles both numbers exactly when both building graphs are complete. For products built from paths or stars, the smaller number is always three, while the larger one is pinned between bounds. They also show that testing whether a given graph can be written as a product of two trees can be done in polynomial time. The results extend what is known about coloring these structured networks and about recognizing them from a bare graph.

Catalog record

CREATORPřemysl Holub, Sandi Klavžar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-06730

Browse the full library · About the Tower of Babel