On S-packing total colorings
Abstract
In this paper, we generalize the concept of packing total coloring by introducing a new concept called the S-packing total coloring. For a graph G and a non-decreasing sequence S=(a1,a2,…) of positive integers, an S-packing total coloring of G is a mapping c: V(G)∪ E(G)→ {1,2,…} such that for any two distinct elements A,B∈ V(G)∪ E(G) with c(A)=c(B)=i, the distance between A and B is at least ai+1. The smallest integer k such that G admits an S-packing total coloring using k colors is called the S-packing total chromatic number of G, denoted by χS''(G). For any sequence S, we establish general lower and upper bounds for χS''(G), and characterize all graphs G with χS''(G)∈{1,2,3}. Furthermore, we investigate S-packing total chromatic numbers of complete bipartite graphs, as well as infinite and finite paths and cycles.
Related
- Density regions, integer certificates and packing colorings of distance graphs
- Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
- Total eight-colorings of maximal planar graphs of maximum degree six
- Total dominating sets and four-colorings of planar triangulations
- A Hajnal-Szemerédi Theorem for Skewed Colorings
BibTeX
@misc{ferme2026spacking,
title = {{On $S$-packing total colorings}},
author = {Jasmina Ferme and Jaka Hedžet and Petra Melicharova and Daša Mesarič Štesl},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10107},
eprint = {2609.10107},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10107},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On S-packing total colorings
AU - Jasmina Ferme
AU - Jaka Hedžet
AU - Petra Melicharova
AU - Daša Mesarič Štesl
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10107
UR - https://arxiv.org/abs/2609.10107
AB - In this paper, we generalize the concept of packing total coloring by introducing a new concept called the S-packing total coloring. For a graph G and a non-decreasing sequence S=(a_1,a_2,…) of positive integers, an S-packing total coloring of G is a mapping c: V(G)∪ E(G)→ {1,2,…} such that for any two distinct elements A,B∈ V(G)∪ E(G) with c(A)=c(B)=i, the distance between A and B is at least a_i+1. The smallest integer k such that G admits an S-packing total coloring using k colors is called the S-packing total chromatic number of G, denoted by χ_S^''(G). For any sequence S, we establish general lower and upper bounds for χ_S^''(G), and characterize all graphs G with χ_S^''(G)∈{1,2,3}. Furthermore, we investigate S-packing total chromatic numbers of complete bipartite graphs, as well as infinite and finite paths and cycles.
ER -