Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.08691 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913099145019392 |
|---|---|
| author | Ferme, Jasmina Štesl, Daša Mesarič |
| author_facet | Ferme, Jasmina Štesl, Daša Mesarič |
| contents | In this paper, we introduce a new concept in graph coloring, namely the \textit{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) \cup E(G) \rightarrow \{1, 2, \ldots\}$ with the property that for any integer $i$, any two distinct elements $A, B \in V(G) \cup 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 \in V(G)$; b) the $\min \{d(a,d), d(a,c),d(b,c), d(b,d)\}+1$ if $\{A, B\} =\{ab, cd\} \subseteq E(G)$; c) the $ \min \{d(a,X), d(b,X)\}+1$ if $\{A, B\}=\{ab, X\}$, where $ab \in E(G)$ and $X \in V(G)$.
The smallest integer $k$ such that $G$ admits a packing total coloring using $k$ colors is called the \textit{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) \in \{1, 2, 3, 4, 5\}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On packing total coloring Ferme, Jasmina Štesl, Daša Mesarič Combinatorics In this paper, we introduce a new concept in graph coloring, namely the \textit{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) \cup E(G) \rightarrow \{1, 2, \ldots\}$ with the property that for any integer $i$, any two distinct elements $A, B \in V(G) \cup 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 \in V(G)$; b) the $\min \{d(a,d), d(a,c),d(b,c), d(b,d)\}+1$ if $\{A, B\} =\{ab, cd\} \subseteq E(G)$; c) the $ \min \{d(a,X), d(b,X)\}+1$ if $\{A, B\}=\{ab, X\}$, where $ab \in E(G)$ and $X \in V(G)$. The smallest integer $k$ such that $G$ admits a packing total coloring using $k$ colors is called the \textit{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) \in \{1, 2, 3, 4, 5\}$. |
| title | On packing total coloring |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.08691 |