pith. sign in

arxiv: 2508.14479 · v2 · submitted 2025-08-20 · 🧮 math.CO

Injective (edge) colorings of generalized Sierpi\'{n}ski graphs

C. K. Bhanupriya , Bo\v{s}tjan Bre\v{s}ar This is my paper

Pith reviewed 2026-05-18 22:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords injective coloringgeneralized Sierpiński graphsinjective chromatic numberinjective edge coloringcycle graphsrecursive graphschromatic index
0
0 comments X

The pith

Generalized Sierpiński graphs over cycles have injective chromatic number exactly 3 for all levels n at least 2.

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

The paper establishes that generalized Sierpiński graphs S_G^n built recursively from any base graph G have injective chromatic number either equal to that of G or one larger. When the base is a cycle of length at least 3, this number is fixed at exactly 3 starting from the second level onward. The same style of bound holds for injective edge colorings when the base is triangle-free, after the third level. A reader would care because the result shows the recursive fractal construction does not force the color count to grow without bound and resolves a prior question specifically for cycle bases.

Core claim

The authors prove that χ_i(S_{C_k}^n) equals 3 for every n ≥ 2 and k ≥ 3. They further prove that χ_i(S_G^n) belongs to the two-element set {χ_i(G), χ_i(G)+1} for arbitrary G and n ≥ 2. For the edge version they show χ_i'(S_{K_3}^n) equals 5 when n ≥ 3 (with smaller values at n=1 and n=2), and that for triangle-free G the edge number after level 3 lies between χ_i'(S_G^3) and that quantity plus one under suitable lifting conditions on the third level.

What carries the argument

The recursive definition of S_G^n from |V(G)| copies of S_G^{n-1} joined according to the edges of G, which permits controlled lifting of colorings from smaller to larger levels.

If this is right

  • The injective chromatic number of any generalized Sierpiński graph stays within one of the base graph's value no matter how many recursive levels are added.
  • Cycle-based versions stabilize immediately at three colors from the second level.
  • Edge injective numbers for triangle-free bases stabilize after the third level within a one-color window.
  • The K_3 base produces edge numbers that reach five by level three and remain there.

Where Pith is reading between the lines

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

  • The same recursive lifting technique might bound other distance-based coloring parameters on these graphs.
  • One could check whether the one-color window persists when the base graph contains many triangles beyond the single K_3 case.
  • The stability result suggests that injective colorings behave more predictably than ordinary chromatic numbers under fractal graph constructions.

Load-bearing premise

Any valid injective coloring of a smaller generalized Sierpiński graph can be extended to the next level by adding at most one new color.

What would settle it

An explicit injective coloring or lower-bound argument showing that some S_{C_k}^n for n ≥ 2 requires four colors.

Figures

Figures reproduced from arXiv: 2508.14479 by Bo\v{s}tjan Bre\v{s}ar, C. K. Bhanupriya.

Figure 1
Figure 1. Figure 1: S 1 C4 (left), S 2 C4 (middle) and S 3 C4 (right); in the latter only labels of extreme vertices are shown. and any n. In addition, for n ≥ 2 they established that χi(S n C4 ) = 3, and suggested a thorough investigation of the injective chromatic number of generalized Sierpi´nski graphs. In particular, concerning the generalized Sierpi´nski graphs over cycles, they suspected that χi(S n Ck ) = 3 holds for … view at source ↗
Figure 2
Figure 2. Figure 2: A sketch of the injective edge coloring of [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Two subgraphs providing lower bounds. 1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Graph Pe; labels in vertices correspond to the numbering of edges of P in [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Sierpi´nski graph over K3 for n = 1, 2 and 3. 3 1 1 1 5 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 3 5 4 4 4 4 4 1 1 4 3 5 5 5 S 3 3 – injective edge coloring of type B [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Type B. Now, we extend the above coloring to an injective edge coloring of S n 3 for n ≥ 4. In fact, we obtain two types of injective edge colorings of S n 3 for each n ≥ 3. For n = 3 these two coloring are 8 [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Coloring of Type A of Sierpi´nski graph S n 3 . For n ≥ 4, we also obtain two injective edge colorings of S n 3 , again called Type A and Type B, that have the same three properties as described for S 3 3 . We achieve this as follows. Note that S n 3 can be obtained from three copies of S n−1 3 , as shown in [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Coloring of Type B of Sierpi´nski graph S n 3 . In addition, we think that the proofs for different orders p may be different, and may be slightly easier for some smaller values of p such as 4 or 5. We pose this as the following problem for which even partial solutions may be interesting. Problem 2. Determine χ ′ i (S n Kp ) for p ≥ 4 and n ≥ 2. Next, we present a general result on the injective chromatic … view at source ↗
Figure 9
Figure 9. Figure 9: A χ ′ i -coloring of S 3 C4 with 3 colors, which leads to the formula χ ′ i (S n C4 ) = 3 for all n ≥ 2. The extreme vertices of S n 3 are shaded. As an application of Theorem 3.3 we determine the injective chromatic indices of the generalized Sierpi´nski graphs over the cycles C4 and C5. First note that χ ′ i (C4) = 2. It is easy to see that χ ′ i (S 2 C4 ) ≥ 3, while from [PITH_FULL_IMAGE:figures/full_f… view at source ↗
Figure 10
Figure 10. Figure 10: A χ ′ i -coloring of S 3 C5 with 4 colors. Now, consider the generalized Sierpi´nski graph over C5. Clearly, χ ′ i (C5) = 3. With some case analysis one can prove that χi(S 2 C5 ) ≥ 4, while [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: A χ ′ i -coloring of S 2 C6 with 3 colors. We believe that for Sierpi´nski graphs over cycles and many other triangle-free graphs as base graphs, Theorem 3.3 can be a used for determining their injective chromatic indices. Neverthe￾less, for graphs G with (many) triangles obtaining a useful general result on χ ′ i (S n G) seems more challenging. Acknowledgments B.B. acknowledges the financial support of t… view at source ↗
read the original abstract

Generalized Sierpi\'{n}ski graphs constitute a distinctive class of fractal-like networks with recursive definition: given a graph $G$, $S_G^1=G$ while $S_G^n$ is obtained from $|V(G)|$ copies of $S_G^{n-1}$ by adding some edges in a prescribed way that reflects the structure of $G$. Many graph invariants have been studied in generalized Sierpi\'{n}ski graphs. In this paper, we focus on their injective colorings, both the vertex and the edge version. Given a graph $G$, a mapping $f$ that assigns an integer from $\{1,\ldots,k\}$ to each vertex (resp.\ edge) of $G$ is an injective (edge) coloring of $G$ if $f(x)=f(y)$ implies that $x$ and $y$ are not in a common triangle nor at distance $2$ for any two vertices (resp.\ edges) $x$ and $y$ in $G$. The minimum number of colors $k$ for which there exists an injective (edge) coloring of $G$ is called the injective chromatic number (resp.\ injective chromatic index) of $G$ and is denoted by $\chi_i(G)$ (resp.\ $\chi_i'(G)$). The vertex version of injective colorings in generalized Sierpi\'{n}ski graphs was studied in an earlier paper, where the authors determined the injective chromatic numbers of standard Sierpi\'{n}ski graphs, and asked about the values when $G$ is a cycle. We resolve this question by proving that $\chi_i(S_{C_k}^n)=3$ for every $n\ge 2$ and every $k\ge 3$. Moreover, we prove an almost conclusive result that $\chi_i(S_G^n)\in \{\chi_i(G),\chi_i(G)+1\}$ for any graph $G$ and any $n\ge 2$. For injective edge colorings we prove that $\chi_i'(S_{K_3}^n)=5$ for all $n\ge 3$, while $\chi_i'(S_{K_3}^2)=4$ and $\chi_i'(S_{K_3}^1)=3$. Furthermore, if $G$ is a triangle-free graph, we prove that $\chi_i'(S_G^n)\in \{\chi_i'(S_G^3),\chi_i'(S_G^3)+1\}$ for all $n\ge 4$, and provide some sufficient conditions on an injective edge coloring of the 3-dimensional Sierpi\'{n}ski graph over $G$, which ensure that $\chi_i'(S_G^n)=\chi_i'(S_G^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 / 3 minor

Summary. The manuscript studies injective vertex colorings and injective edge colorings of generalized Sierpiński graphs S_G^n defined recursively from a base graph G. It proves that χ_i(S_{C_k}^n) = 3 for every n ≥ 2 and k ≥ 3, resolving an open question from prior work. It further claims that χ_i(S_G^n) ∈ {χ_i(G), χ_i(G)+1} for arbitrary G and n ≥ 2. For the edge version, it determines χ_i'(S_{K_3}^n) exactly (3 for n=1, 4 for n=2, 5 for n ≥ 3) and shows that for triangle-free G the value χ_i'(S_G^n) lies in {χ_i'(S_G^3), χ_i'(S_G^3)+1} for n ≥ 4 under stated sufficient conditions on a 3-dimensional coloring.

Significance. If the proofs hold, the work resolves a concrete open question on cycles and supplies a general structural bound on how the injective chromatic number evolves under the Sierpiński recursion. The explicit computations for K_3 and the conditional results for triangle-free graphs are concrete contributions to the study of injective edge colorings on recursively constructed graphs.

minor comments (3)
  1. The statement of the general vertex-coloring bound in the abstract and introduction should explicitly reference the section containing the inductive argument so readers can locate the lifting construction immediately.
  2. Notation for the copies of S_G^{n-1} inside S_G^n is introduced without a diagram or small example; adding a figure for n=2 or n=3 would improve readability of the recursive definition.
  3. The sufficient conditions for the edge-coloring bound on triangle-free graphs are stated in the final section; a short table summarizing which graphs satisfy the conditions would help readers apply the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive evaluation of the manuscript. We are grateful for the recommendation of minor revision and for highlighting the resolution of the open question on cycles as well as the general bounds obtained for injective chromatic numbers and indices under the generalized Sierpiński recursion.

Circularity Check

0 steps flagged

No significant circularity; proofs rely on explicit constructions and induction rather than self-referential reductions

full rationale

The paper defines injective coloring via the standard distance-2 and triangle condition, then proves specific values for cycles and a general bound χ_i(S_G^n) ∈ {χ_i(G), χ_i(G)+1} by direct inductive lifting on the recursive copy construction of S_G^n. No equation equates a claimed result to a fitted parameter or prior self-citation by construction; the earlier paper is cited only for the open question on cycles, which this work resolves independently. The edge-coloring results for K_3 and triangle-free G similarly proceed from explicit colorings and sufficient conditions stated in the present manuscript. All load-bearing steps are self-contained against the given recursive definition and do not reduce to renaming or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are introduced; the work rests on the standard recursive definition of generalized Sierpiński graphs and the definition of injective coloring.

axioms (1)
  • standard math Standard definitions of graphs, distance, triangles, and proper colorings from graph theory.
    Invoked throughout to define the objects and the coloring condition.

pith-pipeline@v0.9.0 · 6069 in / 1207 out tokens · 36363 ms · 2026-05-18T22:45:46.854693+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

35 extracted references · 35 canonical work pages

  1. [1]

    Anitha, I

    J. Anitha, I. Rajasingh, and H. Rashmanlou, Propagating sets in Sierpi´ nski fractal graphs, RAIRO Theor. Inform. Appl. 59 (2025), Paper No. 1

    work page 2025

  2. [2]

    Balakrishnan, M

    K. Balakrishnan, M. Changat, A.M. Hinz, and D.S. Lekha, The median of Sierpi´ nski graphs, Discrete Appl. Math. 319 (2022) 159–170

    work page 2022

  3. [3]

    Bhanupriya, C

    C.K. Bhanupriya, C. Dominic, and M.S. Sunitha, Injective edge coloring of product graphs and some complexity results, Filomat 37 (2023) 3963–3983

    work page 2023

  4. [4]

    Bhanupriya, and M.S

    C.K. Bhanupriya, and M.S. Sunitha, Injective coloring of generalized Mycielskian of graphs, Commun. Comb. Optim. 10 (2025) 463–482

    work page 2025

  5. [5]

    Breˇ sar, and J

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

    work page 2018

  6. [6]

    Breˇ sar, S

    B. Breˇ sar, S. Klavˇ zar, B. Samadi, and I.G. Yero, Injective colorings of Sierpi´ nski-like graphs and Kneser graphs, Graphs. Combin. 41 (2025) 83

    work page 2025

  7. [7]

    Breˇ sar, B

    B. Breˇ sar, B. Samadi, and I. G. Yero, Injective coloring of graphs revisited, Discrete Math. 346 (2023) 113348

    work page 2023

  8. [8]

    Y. Bu, D. Chen, A. Raspaud, and W. Wang, Injective coloring of planar graphs, Discrete Appl. Math. 157 (2009) 663–672

    work page 2009

  9. [9]

    Bujt´ as, E

    Cs. Bujt´ as, E. Sampathkumar, Zs. Tuza, C. Dominic and L. Pushpalatha, 3-consecutive edge coloring of a graph, Discrete Math. 312 (2012) 561–573

    work page 2012

  10. [10]

    Cardoso, J.O

    D.M. Cardoso, J.O. Cerdeira, C. Dominic and J.P. Cruz, Injective edge coloring of graphs, Filomat 33 (2019) 6411—6423

    work page 2019

  11. [11]

    Cranston, S.J

    D. Cranston, S.J. Kim, and G. Yu, Injective colorings of sparse graphs, Discrete Math. 310 (2010) 2965–2973

    work page 2010

  12. [12]

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

    work page 2021

  13. [13]

    Dong, and W

    W. Dong, and W. Lin, Injective coloring of plane graphs with girth 5, Discrete Math. 315 (2014) 120–127

    work page 2014

  14. [14]

    Estaji, and J.A

    E. Estaji, and J.A. Rodr´ ıguez-Vel´ azquez, The strong metric dimension of generalized Sierpi´ nski graphs with pendant vertices, Ars Math. Contemp. 12 (2017) 127–134

    work page 2017

  15. [15]

    Estrada-Moreno, and J.A

    A. Estrada-Moreno, and J.A. Rodr´ ıguez-Vel´ azquez, On the General Randi´ c index of polymeric networks modelled by generalized Sierpi´ nski graphs, Discrete Appl. Math. 263 (2019) 140–151

    work page 2019

  16. [16]

    Ferdjallah, S

    B. Ferdjallah, S. Kerdjoudj, and A. Raspaud, Injective edge-coloring of subcubic graphs, Discrete Math. Algorithms Appl. 14 (2022) 2250040

    work page 2022

  17. [17]

    Foucaud, H

    F. Foucaud, H. Hocquard, and D. Lajou, Complexity and algorithms for injective edge-coloring in graphs, Inform. Process. Lett. 170 (2021) 106121. 15

    work page 2021

  18. [18]

    Geetha, and K

    J. Geetha, and K. Somasundaram, Total coloring of generalized Sierpi´ nski graphs, Australas. J. Combin. 63 (2015) 58–69

    work page 2015

  19. [19]

    Gravier, M

    S. Gravier, M. Kovˇ se, and A. Parreau, Generalized Sierpi´ nski graphs; in: Posters at Eu- roComb’11, Budapest, August 29-September 2, 2011, http://www.renyi.hu/conferences/ ec11/posters/parreau.pdf (2024–08–21)

    work page 2011

  20. [20]

    G. Hahn, J. Kratochv´ ıl, J.ˇSir´ aˇ n, and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002) 179–192

    work page 2002

  21. [21]

    A.M. Hinz, S. Klavˇ zar, C. Petr, The Tower of Hanoi—Myths and Maths , Second Edition, Birkh¨ auser/Springer, Cham, 2018

    work page 2018

  22. [22]

    A.M. Hinz, S. Klavˇ zar, and S.S. Zemljiˇ c, A survey and classification of Sierpi´ nski-type graphs, Discrete Appl. Math. 217 (2017) 565–600

    work page 2017

  23. [23]

    J. Jin, B. Xu, and X. Zhang, On the complexity of injective colorings and its generalizations, Theoret. Comput. Sci. 491 (2013) 119-126

    work page 2013

  24. [24]

    Klavˇ zar, and U

    S. Klavˇ zar, and U. Milutinovi´ c, GraphsS(n,k ) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47 (1997) 95-104

    work page 1997

  25. [25]

    Klavˇ zar, and S.S

    S. Klavˇ zar, and S.S. Zemljiˇ c, Connectivity and some other properties of generalized Sierpi´ nski graphs, Appl. Anal. Discrete Math. 12 (2018) 401–412

    work page 2018

  26. [26]

    Korˇ ze, and A

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

    work page 2019

  27. [27]

    Luˇ zar, and R

    B. Luˇ zar, and R. ˇSkrekovski, Counterexamples to a conjecture on injective colorings, Ars Math. Contemp. 8 (2015) 291–295

    work page 2015

  28. [28]

    Menon, M.R

    M.K. Menon, M.R. Chithra, and K.S. Savitha, Security in Sierpi´ nski graphs, Discrete Appl. Math. 328 (2023) 10–15

    work page 2023

  29. [29]

    Mozafari-Nia, and B

    M. Mozafari-Nia, and B. Omoomi, Injective chromatic number of outerplanar graphs, Tai- wanese J. Math. 22 (2018) 1309–1320

    work page 2018

  30. [30]

    Panda and Priyamvada, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Discrete Appl

    B.S. Panda and Priyamvada, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Discrete Appl. Math. 291 (2021) 68–87

    work page 2021

  31. [31]

    Prabhu, T

    S. Prabhu, T. Janany, and S. Klavˇ zar, Metric dimensions of generalized Sierpi´ nski graphs over squares, Appl. Math. Comput. 505 (2025) Paper No. 129528

    work page 2025

  32. [32]

    Rodr´ ıguez-Vel´ azquez, E.D

    J.A. Rodr´ ıguez-Vel´ azquez, E.D. Rodr´ ıguez-Bazan, and A. Estrada-Moreno, On generalized Sierpi´ nski graphs, Discuss. Math. Graph Theory 37 (2017) 547–560

    work page 2017

  33. [33]

    Samadi, N

    B. Samadi, N. Soltankhah, and I. G. Yero, Injective coloring of product graphs, Bull. Malays. Math. Sci. Soc. 47 (2024) 86

    work page 2024

  34. [34]

    Song, and J

    J. Song, and J. Yue, Injective coloring of some graph operations, Appl. Math. Comput. 264 (2015) 279–283

    work page 2015

  35. [35]

    West, Introduction to Graph Theory (Second Edition), Prentice Hall, USA, 2001

    D.B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, USA, 2001. 16

    work page 2001