pith. sign in

arxiv: 2508.08691 · v2 · submitted 2025-08-12 · 🧮 math.CO

On packing total coloring

Jasmina Ferme , Da\v{s}a Mesari\v{c} \v{S}tesl This is my paper

Pith reviewed 2026-05-18 23:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords packing total coloringpacking total chromatic numbergraph coloringtotal coloringdistance constraintschromatic numbergraph characterization
0
0 comments X

The pith

Packing total coloring uses increasing distances to color vertices and edges, and all graphs with this chromatic number at most 5 are characterized.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces packing total coloring as a mapping from vertices and edges to positive integers where same-colored distinct elements must be separated by at least the color value plus one, using tailored distance measures for different types of pairs. It derives general bounds on the packing total chromatic number and provides a complete characterization of graphs that admit such colorings with one through five colors. This matters because it classifies graphs according to the minimal number of colors needed under these strict packing constraints, which depend on both the graph's structure and the chosen colors.

Core claim

We characterize all graphs G with χ_ρ''(G) ∈ {1, 2, 3, 4, 5} after defining the packing total coloring with specific distance conditions and establishing bounds in terms of maximum degree.

What carries the argument

The packing total coloring with custom distances: usual shortest-path for vertices, min of endpoint distances plus one for two edges, and min of endpoint to vertex distances plus one for an edge and a vertex.

If this is right

  • Graphs can be classified by their packing total chromatic number for small values based on structural properties.
  • Bounds on the number relate directly to the maximum degree of the graph.
  • The characterization provides a way to decide the exact value for any graph that falls into the 1-5 range without constructing the coloring explicitly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar characterizations might be possible for other variants like packing edge coloring or list versions of this coloring.
  • Applying this to specific families like trees or planar graphs could yield explicit formulas or tighter bounds.
  • This distance-based approach may connect to problems in graph labeling or radio coloring where separation conditions are key.

Load-bearing premise

The custom distance definitions for pairs of edges and for vertex-edge pairs correctly capture the intended separation condition without introducing inconsistencies when the same color class mixes vertices and edges.

What would settle it

A graph that the characterization claims has packing total chromatic number 5 but which requires 6 colors in any attempt to color under the given distance rules would disprove the result.

Figures

Figures reproduced from arXiv: 2508.08691 by Da\v{s}a Mesari\v{c} \v{S}tesl, Jasmina Ferme.

Figure 1
Figure 1. Figure 1: An example of T(G). a family of star graphs. We will show that for any positive integer n, χ ′′ ρ (K1,n) = n+ 2, while it is known that χρ(K1,n) = 2. Consequently, for any n, χ ′′ ρ (K1,n)−χρ(K1,n) = n. First, we show that χ ′′ ρ (K1,n) ≥ n + 2. Indeed, it is clear that any packing total col￾oring assigns to the edges of a star pairwise distinct colors, as all edges in this graph are pairwise incident. Add… view at source ↗
Figure 2
Figure 2. Figure 2: A total graph of P5 and notations of its vertices. With the following theorem we provide the exact values and bounds for the packing total chromatic numbers of paths Pn, n ≥ 3. Theorem 5 χ ′′ ρ (Pn) =    4; n = 3 , 5; n ∈ {4, 5} , 6; n ∈ {6, 7} , 7; n ∈ {8, 9} . 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A total graph of C5. total chromatic numbers of cycles Cn, n ≥ 3. Theorem 6 χ ′′ ρ (Cn) =    5; n = 3 , 7; n ∈ {4, 5} , 8; n = 6 , 9; n ∈ {7, 8, 9, 11} , 10; n ∈ {10, 12} . Moreover, for any n ≥ 13, 7 ≤ χ ′′ ρ (Cn) ≤ 11. Proof. Let Cn, n ≥ 3, be a cycle with the vertices denoted as described above. First, let n = 3. Since diam(T(C3)) = 2, any optimal packing coloring of T(C3) uses |V (T(C3)| − α… view at source ↗
Figure 4
Figure 4. Figure 4: Improper and proper packing coloring of T(Cn) - situation 1. u1 8 2 1 3 1 7 2 4 1 6 4 2 5 1 3 1 · · · · · · 1 5 2 1 6 2 1 4 8 1 4 3 1 7 5 2 ↓ u1 2 8 1 3 1 7 2 4 1 6 4 2 5 1 3 1 · · · · · · 1 5 2 1 9 2 1 10 8 1 4 3 1 7 5 11 [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Improper and proper packing coloring of T(Cn) - situation 2. Case 2. Statement (E) holds. Recall that the above presented color pattern for packing coloring of D(1, 2) includes number 7 only three times. From the perspective of a color 7, a packing coloring c of T(Cn) obtained by applying the mentioned color pattern, is problematic only in the cases when a vertex from {un−1, un−1un, un, unu1} receives a co… view at source ↗
Figure 6
Figure 6. Figure 6: Improper and proper packing coloring of T(Cn) - situation 3. u1 8 2 1 3 1 7 2 4 1 6 4 2 5 1 3 1 · · · · · · 1 3 2 1 7 3 1 4 8 1 4 5 1 2 6 1 ↓ u1 2 8 1 3 1 7 2 4 1 6 4 2 5 1 3 1 · · · · · · 1 3 2 1 7 3 1 9 8 1 4 5 1 2 10 11 [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Improper and proper packing coloring of T(Cn) - situation 4. coloring of T(Cn). Hence, in these cases χ ′′ ρ (Cn) ≤ 11. However, three situations remain in which four problematic colors appear (see [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Improper and proper packing coloring of T(Cn) - situation 5. u1 8 2 1 3 1 7 2 4 1 6 4 2 5 1 3 1 · · · · · · 4 2 1 5 2 1 6 2 1 3 8 1 4 3 1 7 ↓ u1 8 2 1 3 1 7 2 4 1 6 4 2 5 1 3 1 · · · · · · 4 2 1 5 2 1 9 1 1 3 10 1 4 3 2 11 [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Improper and proper packing coloring of T(Cn) - situation 6. Remark 7 There exist an infinite number of cycles Cn, n ≥ 27, with χ ′′ ρ (Cn) ≤ 8. Indeed, in the cases when n is a multiple of 27, applying the above presented color pattern for a packing coloring of T(Cn) directly yields a proper packing coloring, which uses only 8 colors. Additionally, for very large cycles Cn, the fact that χρ(D(1, 2)) = 8 i… view at source ↗
Figure 10
Figure 10. Figure 10: Improper and proper packing coloring of T(Cn) - situation 7. namely K1. If a connected graph contains at least two vertices, it contains also at least one edge, which implies that χ ′′ ρ (G) ≥ 3. Therefore, there do not exist graphs with packing total chromatic numbers equal to 2. We also observe that K2 is the only connected graph with the packing total chromatic number equals 3. Indeed, a connected grap… view at source ↗
read the original abstract

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 $\chi_\rho^{''}(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 $\chi_\rho^{''}(G) \in \{1, 2, 3, 4, 5\}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces packing total coloring as a coloring of V(G) ∪ E(G) with positive integers such that any two distinct elements of color i are separated by at least i+1 under a custom distance: ordinary shortest-path distance for vertex pairs, min{d(a,d),d(a,c),d(b,c),d(b,d)}+1 for distinct edges ab,cd, and min{d(a,X),d(b,X)}+1 for an edge ab and vertex X. It establishes general lower and upper bounds on the resulting packing total chromatic number χ_ρ''(G) and gives a complete characterization of all graphs attaining values in {1,2,3,4,5}.

Significance. If the distance definitions are shown to be consistent and the proofs of the classification are complete, the work supplies the first systematic study of a natural packing analogue of total coloring and furnishes an exhaustive list of graphs with small χ_ρ''(G). Such a classification is a concrete, falsifiable contribution that can serve as a benchmark for further results on the parameter.

major comments (2)
  1. [Abstract] Abstract (distance definitions): the edge-edge distance min{d(a,d),d(a,c),d(b,c),d(b,d)}+1 and the vertex-edge distance min{d(a,X),d(b,X)}+1 are introduced without an accompanying lemma verifying that these quantities are symmetric, at least 1 for distinct elements, and that they correctly enforce the global packing condition when a single color class contains both vertices and edges. The central characterization of graphs with χ_ρ''(G) ∈ {1,2,3,4,5} is load-bearing on this point; any pair that receives the same color i yet violates the intended i+1 separation under ordinary graph distance would invalidate the classification.
  2. [Characterization theorem] Characterization theorem (presumably §4 or §5): the exhaustive case analysis for small values assumes that the custom distances produce a well-defined packing condition across mixed element types. The manuscript should supply an explicit verification (or counter-example search) that no two elements closer than i+1 in the underlying graph can be assigned the same color i under the given min+1 rules; without this, the completeness claim for χ_ρ''(G) ≤ 5 cannot be confirmed.
minor comments (2)
  1. [Introduction] The introduction would benefit from a short comparison of χ_ρ''(G) with the ordinary packing chromatic number and the total chromatic number to clarify the novelty.
  2. [Characterization section] A few proofs in the characterization section rely on case distinctions that could be made more explicit by indicating precisely which distance rule is applied at each step.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to strengthen the foundational definitions in our introduction of packing total coloring. The comments correctly note that the custom distance functions for edge-edge and vertex-edge pairs require explicit verification to support the packing condition and the classification results. We will revise the manuscript by adding a dedicated lemma that rigorously establishes the required properties of these distances.

read point-by-point responses

  1. Referee: [Abstract] Abstract (distance definitions): the edge-edge distance min{d(a,d),d(a,c),d(b,c),d(b,d)}+1 and the vertex-edge distance min{d(a,X),d(b,X)}+1 are introduced without an accompanying lemma verifying that these quantities are symmetric, at least 1 for distinct elements, and that they correctly enforce the global packing condition when a single color class contains both vertices and edges. The central characterization of graphs with χ_ρ''(G) ∈ {1,2,3,4,5} is load-bearing on this point; any pair that receives the same color i yet violates the intended i+1 separation under ordinary graph distance would invalidate the classification.

    Authors: We agree that an explicit verification is needed. In the revised version we will insert a new lemma (in the preliminaries section) proving that the defined distances are symmetric, at least 1 for distinct elements, and that they correctly enforce the i+1 separation requirement under ordinary graph distance even when a color class mixes vertices and edges. This lemma will directly confirm that the packing condition is well-defined across all element types. revision: yes

  2. Referee: [Characterization theorem] Characterization theorem (presumably §4 or §5): the exhaustive case analysis for small values assumes that the custom distances produce a well-defined packing condition across mixed element types. The manuscript should supply an explicit verification (or counter-example search) that no two elements closer than i+1 in the underlying graph can be assigned the same color i under the given min+1 rules; without this, the completeness claim for χ_ρ''(G) ≤ 5 cannot be confirmed.

    Authors: The requested verification will be supplied by the new lemma described above, which shows that the min+1 rules prevent any two elements violating the ordinary i+1 separation from receiving the same color i. With this addition the case analysis underlying the characterization of graphs with χ_ρ''(G) ≤ 5 rests on a formally verified foundation. We have re-checked the proofs and they remain valid once the lemma is in place. revision: yes

Circularity Check

0 steps flagged

No circularity: new concept defined from first principles and characterized directly

full rationale

The paper defines packing total coloring and the associated distance functions explicitly in the abstract and introduction, then derives bounds and the characterization of graphs with χ_ρ''(G) ∈ {1,2,3,4,5} from those definitions using standard graph distance and case analysis. No equations reduce a claimed prediction to a fitted input, no self-citation chain supports the central premise, and the distance rules are stated outright rather than imported via ansatz or prior author work. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph-theoretic distance and the newly introduced separation rule; no numerical parameters are fitted and no new physical entities are postulated.

axioms (1)
  • standard math Standard shortest-path distance on vertices and the defined min-distance rules for edge-edge and vertex-edge pairs.
    Invoked in the definition of packing total coloring.

pith-pipeline@v0.9.0 · 5884 in / 1084 out tokens · 24483 ms · 2026-05-18T23:33:37.313759+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Balogh, A

    J. Balogh, A. Kostochka, X. Liu, Packing chromatic number of subcubic graphs , Discrete Math. 341 (2018) 474–483

    work page 2018

  2. [2]

    Breˇ sar, J

    B. Breˇ sar, J. Ferme,An infinite family of subcubic graphs with unbounded packing chromatic number, Discrete Math. 341 (2018) 2337–2342

    work page 2018

  3. [3]

    Breˇ sar, J

    B. Breˇ sar, J. Ferme, S. Klavˇ zar, D. F. Rall,A survey on packing colorings, Discuss. Math. Graph Theory 40 (2020) 923–970

    work page 2020

  4. [4]

    Breˇ sar, S

    B. Breˇ sar, S. Klavˇ zar, D.F. Rall,On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math. 155 (2007) 2303–2311

    work page 2007

  5. [5]

    Dliou, Independence, matching and packing coloring of the iterated Mycielskian of graphs, Discrete Appl

    K. Dliou, Independence, matching and packing coloring of the iterated Mycielskian of graphs, Discrete Appl. Math. 361 (2025) 22–33

    work page 2025

  6. [6]

    Gastineau and O

    N. Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019) 63–75

    work page 2019

  7. [7]

    Goddard, S.M

    W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris and D.F. Rall,Broad- cast chromatic numbers of graphs , Ars Combin. 86 (2008) 33–49

    work page 2008

  8. [8]

    G˝ oz˝ upek, I

    D. G˝ oz˝ upek, I. Peterin,Grundy packing coloring of graphs , Discrete Appl. Math. 371 (2025) 17–30. 20

    work page 2025

  9. [9]

    Hocquard, D

    H. Hocquard, D. Lajou, B. Luˇ zar, Between proper and strong edge-colorings of subcubic graphs, J. Graph Theory 101 (4) (2022), 686–716

    work page 2022

  10. [10]

    Junosza-Szaniawski, H

    K. Junosza-Szaniawski, H. Grochowski, Partial packing coloring and quasi-packing coloring of the triangular grid , Discrete Math. 348 (2025)

    work page 2025

  11. [11]

    A. I. Kristiana, S. M. Citra, Dafik, R. Alfarisi, R. Adawiyah, On The Packing k-Coloring of Some Family Trees , Stat. optim. inf. comput. 13 (3) (2024), 1291– 1298

    work page 2024

  12. [12]

    X. Liu, G. Yu, On the (12, 24)-packing edge-coloring of subcubic graphs , arXiv:2402.18353 [math.CO] (28 Feb 2024)

    work page arXiv 2024

  13. [13]

    X. Liu, M. Santana, T. Short, Every subcubic multigraph is (1, 27)-packing edge- colorable, J. Graph Theory, 104 (2023), 851–885

    work page 2023

  14. [14]

    Togni, On packing colorings of distance graphs, Discrete Appl

    O. Togni, On packing colorings of distance graphs, Discrete Appl. Math. 167 (2014) 280–289

    work page 2014

  15. [15]

    W. Yang, B. Wu, On S-packing edge-colorings of graphs with small edge weight , Appl. Math. Comput. 418 (2022). 21

    work page 2022