pith. sign in

arxiv: 2605.03912 · v1 · submitted 2026-05-05 · 🧮 math.CO · cs.DM

Packing chromatic critical graphs with radius at most 2

Asl{\i}han G\"ur , Didem G\"oz\"upek , Hadi Alizadeh This is my paper

Pith reviewed 2026-05-07 15:14 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords packing chromatic numbercritical graphsradiuscactus graphsi-packingdistance constraintsgraph partitioning
0
0 comments X

The pith

Packing chromatic critical graphs with radius 1 receive a structural characterization, and the cactus ones with radius 2 and diameter 2 or 3 are completely determined.

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

The paper focuses on minimal graphs for the packing chromatic number, the smallest k such that vertices can be partitioned into sets where the i-th set has all pairs at distance greater than i. Critical graphs are those minimal in the sense that every proper subgraph has a strictly smaller packing chromatic number. By restricting attention to graphs of radius 1, where all vertices lie at distance at most 1 from some central vertex, the authors supply an explicit structural description of every critical example. They then restrict further to cactus graphs, which are graphs in which any two cycles share at most one vertex, and give a complete list of the critical ones that also have radius 2 and diameter 2 or 3. These determinations matter because they identify the exact smallest structures that force a given value of the packing chromatic number inside these bounded-radius families.

Core claim

The central claim is that χ_ρ-critical graphs with radius 1 admit a structural characterization, while the χ_ρ-critical cactus graphs with radius 2 and diameter 2 or 3 are completely determined by exhaustive examination of possible configurations under the given distance constraints.

What carries the argument

χ_ρ-critical graphs, defined as those G for which χ_ρ(H) < χ_ρ(G) whenever H is any proper subgraph of G, together with the radius-1 condition that permits direct structural description and the cactus property that permits exhaustive enumeration when diameter is also bounded.

If this is right

  • Every χ_ρ-critical graph of radius 1 must match one of the structures in the given characterization.
  • The only χ_ρ-critical cactus graphs with radius 2 and diameter 2 or 3 are those explicitly identified.
  • Any graph belonging to these classes has a packing chromatic number that can be read off from its relation to the listed critical examples.

Where Pith is reading between the lines

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

  • The structural results may reduce the problem of computing the packing chromatic number for any radius-1 graph to a check against the finite list of critical forms.
  • The exhaustive method used for small-diameter cacti suggests similar complete determinations could be attempted for other hereditary classes with bounded radius.
  • Knowledge of these minimal examples clarifies how local cycle and distance structure forces increases in the packing chromatic number.

Load-bearing premise

The standard definitions of i-packing, packing chromatic number, and χ_ρ-critical graphs hold without additional constraints, and the radius and diameter limits allow exhaustive case analysis on cactus graphs.

What would settle it

A graph with radius 1 that is χ_ρ-critical yet fails to match the stated structural characterization, or a cactus graph with radius 2 and diameter 2 or 3 that is χ_ρ-critical yet is absent from the complete list provided.

Figures

Figures reproduced from arXiv: 2605.03912 by Asl{\i}han G\"ur, Didem G\"oz\"upek, Hadi Alizadeh.

Figure 1
Figure 1. Figure 1: The wheel graph W6. In Lemma 3.7, we characterize χρ-critical graphs with radius 1 and diameter 2 that have a universal cut vertex, that is, a cut vertex adjacent to every other vertex. Our proof will use a corollary of the next result due to Haynes et al. [19]. Lemma 3.5 [19] A graph G has α(G) ̸= α(G − e) for all e ∈ E if and only if for each edge e = uv there exists a maximum independent set I where u ∈… view at source ↗
Figure 3
Figure 3. Figure 3: G (4) 2 (1, 2; 2, 1). 4.2.1 χρ-critical cactus graphs with radius 2 and diameter 3, where C5 is the main block We now proceed with cactus graphs with radius 2 and diameter 3 with C5 as their main block. The next result provides the packing chromatic number of a graph G ∈ G(5) 1 (k1, m1). Proposition 4.7 Let G ∈ G(5) 1 (k1, m1) and k1, m1 ≥ 0. Then χρ(G) =    4, if m1 = 0, m1 + 3, if m1 ≥ 1. Proof. Let G… view at source ↗
Figure 4
Figure 4. Figure 4: G (5) 1 (2, 2)-An example of a 5-packing coloring. Proposition 4.8 Let G ∈ G(5) 1 (k1, m1). If k1 > 0, then G is not χρ-critical. Proof. Suppose that G ∈ G(5) 1 (k1, m1) with k1 > 0 is a χρ-critical graph, that is, G contains at least one leaf v. Let e = x1v be the edge incident to v, where x1 is the cut vertex of G. Since v is a leaf, the removal of e splits the graph G − e into two components H1 = G[V (G… view at source ↗
Figure 5
Figure 5. Figure 5: H(1, 1; 2, 0). Lemma 4.12 Let G ∈ G(5) 2 (k1, m1; k2, m2) with k1, k2 ≥ 0, m1, m2 ≥ 0. Then G is not χρ-critical. Proof. Let G ∈ G(5) 2 (k1, m1; k2, m2) and t = m1 +m2. We first consider t = 0. Then by the definition of G (5) 2 (k1, m1; k2, m2), k1 ≥ 1 and k2 ≥ 1. Hence, G has at least two K2 blocks. Consider an edge e contained in a K2 block. Since C5 is a subgraph 17 view at source ↗
Figure 6
Figure 6. Figure 6: Friendship graph T3. Observation 4.13 Let Tn be a friendship graph with n ≥ 1. Then χρ(Tn) = n + 2. Proof. We know that Tn with n ≥ 2 has diameter 2 and α(Tn) = n. Then χρ(Tn) = n + 2 by Lemma 3.2. This rule trivially holds for n = 1 since T1 ∼= C3. □ Proposition 4.14 Let G ∈ G(4) 1 (k1, m1) and k1, m1 ≥ 0. Then χρ(G) =    3, if m1 = 0, m1 + 2, if m1 ≥ 1. Proof. Let G ∈ G(4) 1 (k1, m1). For the first ca… view at source ↗
read the original abstract

For a graph $G$ with vertex set $V(G)$ and a positive integer $i$, an $i$-packing in $G$ is a subset $X$ of $V(G)$ such that the distance between any two distinct vertices of $X$ is greater than $i$. The packing chromatic number of $G$, denoted by $\chi_{\rho}(G)$, is the smallest positive integer $k$ for which there exists a partition $X_1, X_2, \ldots, X_k$ of $V(G)$ such that $X_i$ is an $i$-packing in $G$ for every $i \in [k]$. A graph $G$ is called $\chi_\rho$-critical if $\chi_\rho(H) < \chi_\rho(G)$ holds for every proper subgraph $H$ of $G$. In this paper, we provide a structural characterization of $\chi_{\rho}$-critical graphs with radius $1$, and completely determine the $\chi_{\rho}$-critical cactus graphs with radius $2$ and diameter $2$ or $3$.

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

0 major / 2 minor

Summary. The manuscript provides a structural characterization of χ_ρ-critical graphs with radius 1 and completely determines all χ_ρ-critical cactus graphs with radius 2 and diameter 2 or 3. The arguments rely on the standard definitions of i-packings and χ_ρ-criticality together with exhaustive case analysis on the restricted classes.

Significance. If the characterizations are correct, the work advances the understanding of packing chromatic numbers by giving explicit structural descriptions for critical graphs in two restricted families where exhaustive enumeration is feasible. The radius-1 case yields a clean universal-vertex description, while the cactus determinations for small diameter supply concrete families that can serve as test cases or building blocks for broader results on χ_ρ.

minor comments (2)
  1. §1: The introduction states the main results but does not explicitly reference the theorem numbers that contain the characterizations; adding forward references would improve readability.
  2. Definition 2.3: The notation for the packing chromatic number is introduced after the criticality definition; moving the χ_ρ definition earlier would make the criticality statement self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. No specific major comments were raised in the report, so there are no individual points requiring detailed rebuttal or changes beyond any minor editorial adjustments that may arise during revision.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via definitions and case analysis

full rationale

The paper's central results are a structural characterization of χ_ρ-critical graphs of radius 1 and a complete determination of χ_ρ-critical cacti of radius 2 with diameter 2 or 3. These rest on the standard definitions of i-packings, packing chromatic number, and χ_ρ-criticality (given explicitly in the abstract) together with exhaustive enumeration permitted by the radius/diameter bounds. No load-bearing step invokes a fitted parameter renamed as a prediction, a self-citation chain for a uniqueness theorem, an ansatz smuggled via prior work, or a renaming of a known empirical pattern. The derivation chain therefore does not reduce to its own inputs by construction and remains independent of the present paper's fitted values or self-referential premises.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest entirely on standard graph-theoretic definitions and axioms with no new free parameters, invented entities, or ad-hoc assumptions beyond the radius and cactus restrictions stated in the abstract.

axioms (1)
  • standard math Standard definitions of graphs, vertex distances, i-packings, packing chromatic number χ_ρ(G), and χ_ρ-critical graphs.
    Invoked throughout the abstract to define the objects being characterized.

pith-pipeline@v0.9.0 · 5505 in / 1153 out tokens · 52451 ms · 2026-05-07T15:14:30.139587+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

27 extracted references · 27 canonical work pages

  1. [1]

    Balogh, A

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

    work page 2018

  2. [2]

    Boˇ zovi´ c, I

    D. Boˇ zovi´ c, I. Peterin, A note on the packing chromatic number of lexicographic products, Discrete Appl. Math. 293 (2021) 34–37

    work page 2021

  3. [3]

    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

  4. [4]

    Breˇ sar, J

    B. Breˇ sar, J. Ferme, Graphs that are critical for the packing chromatic number, Discuss. Math. Graph Theory 42 (2022) 569–589

    work page 2022

  5. [5]

    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

  6. [6]

    Breˇ sar, J

    B. Breˇ sar, J. Ferme, Packing coloring of Sierpi´ nski-type graphs, Aequationes Math. 92 (2018) 1091–1118

    work page 2018

  7. [7]

    Breˇ sar, N

    B. Breˇ sar, N. Gastineau, O. Togni, Packing colorings of subcubic outerplanar graphs, Aequationes Math. 94(5) (2020) 945–967

    work page 2020

  8. [8]

    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

  9. [9]

    Breˇ sar, S

    B. Breˇ sar, S. Klavˇ zar, D. F. Rall, K. Wash, Packing chromatic number versus chromatic and clique number, Aequationes Math. 92 (2018) 497–513

    work page 2018

  10. [10]

    F. Deng, Z. Shao, A. Vesel, On the packing coloring of base-3 Sierpi´ nski graphs andH-graphs, Aequationes Math. 95 (2021) 329–341

    work page 2021

  11. [11]

    Ekstein, P

    J. Ekstein, P. Holub, O. Togni, The packing coloring of distance graphsD(k, t), Discrete Appl. Math. 167 (2014) 100–106

    work page 2014

  12. [12]

    Ferme, A characterization of 4-χ ρ-(vertex-)critical graphs, Filomat 36 (2022) 6481–6501

    J. Ferme, A characterization of 4-χ ρ-(vertex-)critical graphs, Filomat 36 (2022) 6481–6501

    work page 2022

  13. [13]

    Fiala, P.A

    J. Fiala, P.A. Golovach, Complexity of the packing coloring problem for trees, Discrete Appl. Math. 158 (2010) 771–778

    work page 2010

  14. [14]

    Fiala, S

    J. Fiala, S. Klavˇ zar, B. Lidick´ y, The packing chromatic number of infinite product graphs, European J. Combin. 30 (2009) 1101–1113

    work page 2009

  15. [15]

    Furmańczyk, D

    H. Furma´ nczyk, D. G¨ oz¨ upek, S.¨Ozkan, Packing coloring of graphs with long paths, arXiv:2511.12761 [math.CO] (2025) 27

    work page arXiv 2025

  16. [16]

    Gastineau, P

    N. Gastineau, P. Holub, O. Togni, On the packing chromatic number of subcu- bic outerplanar graphs, Discrete Appl. Math. 255 (2019) 209–221

    work page 2019

  17. [17]

    Goddard, S.M

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

    work page 2008

  18. [18]

    Gregor, J

    P. Gregor, J. Kranjc, B. Luˇ zar, K.ˇStorgel, Packing coloring of hypercubes with extended Hamming codes, Discrete Appl. Math. 359 (2024) 269–277

    work page 2024

  19. [19]

    T. W. Haynes, L. M. Lawson, R. C. Brigham, R. D. Dutton, Changing and unchanging of the graphical invariants: minimum and maximum degree, max- imum clique size, node independence number and edge independence number, Congr. Numer. 72 (1990) 239–252

    work page 1990

  20. [20]

    M. Kim, B. Lidick´ y, T. Masaˇ r´ ık, F. Pfender, Notes on complexity of packing coloring, Inform. Process. Lett. 137 (2018) 6–10

    work page 2018

  21. [21]

    Klavˇ zar, D.F

    S. Klavˇ zar, D.F. Rall, Packing chromatic vertex-critical graphs, Discrete Math. Theor. Comput. Sci. 21(3) (2019) #8

    work page 2019

  22. [22]

    Korˇ ze, A

    D. Korˇ ze, A. Vesel, Packing coloring of generalized Sierpi´ nski graphs, Discrete Math. Theor. Comput. Sci. 21(3) (2019) #7

    work page 2019

  23. [23]

    La¨ ıche, I

    D. La¨ ıche, I. Bouchemakh,´E. Sopena, Packing coloring of some undirected and oriented coronae graphs, Discuss. Math. Graph Theory 37 (2017) 665–690

    work page 2017

  24. [24]

    Martin, F

    B. Martin, F. Raimondi, T. Chen, J. Martin, The packing chromatic number of the infinite square lattice is between 13 and 15, Discrete Appl. Math. 225 (2017) 136–142

    work page 2017

  25. [25]

    D.F. Rall, B. Breˇ sar, A.S. Finbow, S. Klavˇ zar, On the packing chromatic num- ber of trees, Cartesian products and some infinite graphs, Electron. Notes Dis- crete Math. 30 (2008) 57–61

    work page 2008

  26. [26]

    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

  27. [27]

    West, Introduction to graph theory, Prentice Hall, Newyork, 2001

    D.B. West, Introduction to graph theory, Prentice Hall, Newyork, 2001. 28

    work page 2001