2025/08/12 by Jasmina Ferme, Ferme, Jasmina, Daša Štesl +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2508.08691
In this paper, we introduce a new concept in graph coloring, namely the packing total coloring, which extends the idea of packing coloring to both the vertices and the edges of a given graph. More precisely, for a graph G, a packing total coloring is a mapping c: V(G) ∪ E(G) → \1, 2, …\ with the property that for any integer i, any two distinct elements A, B ∈ V(G) ∪ E(G) with c(A) = c(B) = i must be at distance at least i+1 from each other. Note that the distance between A and B means: a) the usual shortest-path distance between A and B if A, B ∈ V(G); b) the min \d(a,d), d(a,c),d(b,c), d(b,d)\+1 if \A, B\ =\ab, cd\ ⊆ E(G); c) the min \d(a,X), d(b,X)\+1 if \A, B\=\ab, X\, where ab ∈ E(G) and X ∈ V(G). The smallest integer k such that G admits a packing total coloring using k colors is called the packing total chromatic number, denoted by χρ''(G). In addition to introducing this new concept, we provide lower and upper bounds for the packing total chromatic numbers of graphs. Furthermore, we consider packing total chromatic numbers of graphs from the perspective of their maximum degrees and characterize all graphs G with χρ''(G) ∈ \1, 2, 3, 4, 5\.