pith. sign in

arxiv: 2605.16680 · v2 · pith:FRRJD6YRnew · submitted 2026-05-15 · 🧮 math.CO

On the Packing Coloring Gap of Graphs

Batoul Tarhini , Didem G\"oz\"upek This is my paper

Pith reviewed 2026-05-20 15:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords packing chromatic numberpacking coloringgraph gapcaterpillar treescorona operationtreesvertex deletion
0
0 comments X

The pith

The packing coloring gap is the largest drop in packing chromatic number after deleting one vertex, and this gap equals one for every caterpillar.

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

The paper defines the packing coloring gap of a graph as the maximum amount by which its packing chromatic number decreases when any single vertex is removed. It then computes this gap exactly for the class of caterpillar trees by using their path backbone and pendant leaves. The same exact value is shown to hold after applying the corona operation with K1 to a caterpillar. The work also constructs families of graphs that achieve packing coloring gaps of zero, one, and any prescribed positive integer.

Core claim

By direct calculation from the definition, the packing chromatic number of a caterpillar drops by at most one upon deletion of any vertex, so the packing coloring gap of every caterpillar is exactly one; the same exact gap holds for the corona of a caterpillar with K1.

What carries the argument

The packing coloring gap, defined as the maximum over all vertices v of (packing chromatic number of G minus packing chromatic number of G minus v).

If this is right

  • Every caterpillar has packing coloring gap exactly one.
  • The corona of any caterpillar with K1 also has packing coloring gap exactly one.
  • There exist graphs whose packing coloring gap is zero.
  • There exist graphs whose packing coloring gap is one.
  • There exist graphs whose packing coloring gap is arbitrarily large.

Where Pith is reading between the lines

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

  • The bounded gap for caterpillars isolates a structural feature that may fail in non-caterpillar trees.
  • The corona construction shows that certain local attachments preserve the gap value.
  • The existence of graphs with unbounded gaps indicates that the one-vertex stability property is special to restricted tree classes.

Load-bearing premise

The structural features of caterpillars allow the packing chromatic numbers of the original graph and every one-vertex-deleted subgraph to be read off directly from the definition.

What would settle it

A caterpillar tree in which deletion of some vertex lowers the packing chromatic number by two or more.

Figures

Figures reproduced from arXiv: 2605.16680 by Batoul Tarhini, Didem G\"oz\"upek.

Figure 1
Figure 1. Figure 1: A configuration that appears as a subgraph of [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Caterpillars T with χp(T) = k and µp(T) = 1 for k = 3, 4, 5, 6. Numbers in spine vertices shows a packing coloring for T. . For k = 7, we explain the example as follows. Klavžar et al. showed in [8] that if n ≥ 35, then attaching to every vertex of Pn precisely (or more) 6 leaves yields a caterpillar T with χp(T) = 7. To construct our example, let T be the caterpillar with n = 35 and attach to each vertex … view at source ↗
Figure 3
Figure 3. Figure 3: The graph obtained by reinserting the vertex [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A family of cographs with unbounded packing coloring gap. [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
read the original abstract

The packing chromatic number of a graph is the minimum number of colors for which the graph admits a packing coloring. This distance-based parameter may change under local structural modifications of the graph. In this paper, we introduce the packing coloring gap, defined as the maximum decrease in the packing chromatic number caused by the deletion of a single vertex. We focus on trees and determine the packing coloring gap for caterpillars. We further extend these results to caterpillars under the corona operation with K1. In addition, we present examples of graphs with packing coloring gap zero, one, and arbitrarily large.

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 / 3 minor

Summary. The paper introduces the packing coloring gap of a graph G as the maximum value of χ_p(G) − χ_p(G − v) over all vertices v, where χ_p denotes the packing chromatic number. It determines this gap exactly for all caterpillars by case analysis on the spine and pendant leaves, extends the determination to the corona of any caterpillar with K_1, and constructs families of graphs realizing gap values 0, 1, and arbitrarily large.

Significance. If the determinations are correct, the work defines a new, natural stability parameter for the packing chromatic number and computes it exactly on two infinite families of trees whose structure permits exhaustive local case analysis. The explicit constructions showing unbounded gaps are useful for understanding the possible range of the parameter. The paper is credited for grounding the results in the standard definition of packing coloring without additional ad-hoc constraints and for providing concrete, falsifiable values for these graph classes.

major comments (2)
  1. [§3, Theorem 3.1] §3, Theorem 3.1: the case analysis for a caterpillar whose spine has length at least 4 appears to omit the subcase in which the deleted vertex is an internal spine vertex of degree 3 with two pendant leaves; the distance-2 constraints after deletion are not explicitly recomputed for this configuration.
  2. [§4, Corollary 4.3] §4, Corollary 4.3: the claimed gap of 2 for the K_1-corona of a caterpillar is stated without an accompanying lower-bound construction or explicit coloring of the original corona graph; the upper bound follows from the caterpillar result but the matching lower bound requires verification that no single vertex deletion reduces χ_p by more than 2.
minor comments (3)
  1. [Introduction] The definition of the packing coloring gap in the introduction should explicitly note that the quantity is taken to be non-negative (i.e., the maximum decrease) and clarify the convention when χ_p(G − v) > χ_p(G) for some v.
  2. [Figure 2] Figure 2 (corona example) would benefit from labeling the spine vertices and indicating which vertex is deleted in the accompanying text.
  3. [Introduction] A short remark comparing the new gap to the known sensitivity of the ordinary chromatic number or the distance-2 chromatic number under vertex deletion would help situate the parameter.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, indicating where revisions will be made to improve clarity and completeness.

read point-by-point responses

  1. Referee: [§3, Theorem 3.1] §3, Theorem 3.1: the case analysis for a caterpillar whose spine has length at least 4 appears to omit the subcase in which the deleted vertex is an internal spine vertex of degree 3 with two pendant leaves; the distance-2 constraints after deletion are not explicitly recomputed for this configuration.

    Authors: We thank the referee for identifying this potential gap in explicitness. While the general case analysis for internal spine vertices of degree at least 3 (including those with two pendant leaves) is covered through the distance-based packing constraints in the proof of Theorem 3.1, we agree that recomputing the distance-2 constraints specifically for this configuration would enhance readability. In the revised manuscript we will insert a dedicated subcase paragraph that explicitly verifies the effect on colors at distance 2 and confirms that the packing chromatic number decreases by no more than the stated gap value. revision: yes

  2. Referee: [§4, Corollary 4.3] §4, Corollary 4.3: the claimed gap of 2 for the K_1-corona of a caterpillar is stated without an accompanying lower-bound construction or explicit coloring of the original corona graph; the upper bound follows from the caterpillar result but the matching lower bound requires verification that no single vertex deletion reduces χ_p by more than 2.

    Authors: The referee correctly notes that an explicit lower-bound example would strengthen the statement. The upper bound is indeed inherited from the caterpillar result. For the lower bound, the corona construction ensures that the added pendant vertices do not permit any single deletion to reduce χ_p by more than 2, because the new leaves can be colored with colors already present without violating the packing condition at distance 2. To make this fully verifiable, we will add a concrete example in the revised version: a specific caterpillar corona together with an optimal packing coloring of the full graph and the reduced coloring after deletion of a suitable vertex, demonstrating that the gap is exactly 2. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via direct structural analysis

full rationale

The paper introduces the packing coloring gap as a new parameter defined directly as the maximum drop in packing chromatic number upon single-vertex deletion. For caterpillars (spine path plus pendants) and their K1-coronas, the results follow from exhaustive case analysis on color placements and deletion effects using only the standard distance-2 packing constraints and the graphs' explicit structure. No equations reduce a claimed prediction to a fitted input by construction, no load-bearing self-citation chains appear, and no ansatz or uniqueness theorem is smuggled in. The derivation remains independent of its own outputs and is externally verifiable by checking the definitions on the described graph families.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper adds one new defined quantity and applies it to known graph classes; relies on standard background but introduces no free parameters or external entities.

axioms (1)
  • standard math Standard definitions of graphs, trees, caterpillars, packing coloring, and corona operation with K1.
    The work builds directly on established combinatorial graph theory concepts without new unproved lemmas stated in the abstract.
invented entities (1)
  • packing coloring gap no independent evidence
    purpose: To quantify the maximum decrease in packing chromatic number caused by deleting one vertex.
    Newly defined parameter; no independent evidence or falsifiable prediction outside the paper is mentioned.

pith-pipeline@v0.9.0 · 5616 in / 1213 out tokens · 65176 ms · 2026-05-20T15:51:27.010432+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Urenda, J.A

    A.M. Urenda, J.A. Lingcong, N. Batucan, J. Adanza, M. Baldado Jr., Packing Chromatic Number of the Join of Some Classes of Graphs, in: International Mathematical Forum, V17 (2022), no. 2, 75 - 87

    work page 2022

  2. [2]

    Brešar, S

    B. Brešar, S. Klavžar, D. F. Rall, and K. Wash, Packing chromatic num- ber under local changes in a graph,Discrete Mathematics, 340 (2017), 1110–1115

    work page 2017

  3. [3]

    Brešar, S

    B. Brešar, S. Klavžar, and D. F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees,Discrete Applied Mathematics, 155 (2007), 2303–2311

    work page 2007

  4. [4]

    Sloper, An eccentric coloring of trees,Australasian Journal Of Com- binatorics, 29 (2004), 309–321

    C. Sloper, An eccentric coloring of trees,Australasian Journal Of Com- binatorics, 29 (2004), 309–321. 21

    work page 2004

  5. [5]

    Argiroffo, G

    G. Argiroffo, G. Nasini, and P. Torres, The packing coloring problem for lobsters and partner limited graphs,Discrete Applied Mathematics, 164 (2014) Part 2, 373-382

    work page 2014

  6. [6]

    Furmańczyk, D

    H. Furmańczyk, D. Gözüpek, and S. Özkan, Packing coloring of graphs with long paths,arXiv preprint, arXiv:2511.12761 (2025). https://doi.org/10.48550/arXiv.2511.12761

    work page doi:10.48550/arxiv.2511.12761 2025

  7. [7]

    Brešar, J

    B. Brešar, J. Ferme, S. Klavžar, D. F. Rall, A survey on packing col- orings,Discussiones Mathematicae, Graph Theory 40, No. 4 (2020), 923-970

    work page 2020

  8. [8]

    3 (2019), Paper No

    S.Klavžar, D.F.Rall, Packingchromaticvertex-criticalgraphs,Discrete Mathematics and Theoretical Computer Science,21, No. 3 (2019), Paper No. 8

    work page 2019

  9. [9]

    Goddard, S.M

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

    work page 2008