2025/08/20 by Bhanupriya, C. K., Brešar, Boštjan
#05C15 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.14479
Generalized Sierpiński graphs constitute a distinctive class of fractal-like networks, whose self-similar properties have attracted growing attention. In particular, a number of graph invariants have been studied in generalized Sierpiński graphs. In this paper, we focus on injective colorings of this class of graphs, both the vertex and the edge version. The vertex version of injective colorings in generalized Sierpiński graphs was initiated in [Injective colorings of Sierpiński-like graphs and Kneser graphs,Graphs. Combin. 41 (2025) 83], where the authors determined the injective chromatic numbers of the standard Sierpiński graphs (which are those whose base graph is a clique) and asked about the values when the base graph is a cycle. We resolve this question by proving that χi(SCkn)=3 for every n≥ 2 and every k≥ 3, which follows from a more general result on generalized Sierpi' nski graphs SGn with arbitrary base graphs G. Moreover, we prove (an almost conclusive result) that χi(SGn)∈ \χi(G),χi(G)+1\ for any graph G and any n≥ 2. Injective edge colorings appear to be more difficult, especially in graphs with triangles. On a positive note, we prove that χi'(SK3n)=5 for all n≥ 3. Furthermore, if G is a triangle-free graph, we prove that χi'(SGn)∈ \χi'(SG3),χi'(SG3)+1\ for all n≥ 4, and provide some sufficient conditions on an injective edge coloring of the 3-dimensional Sierpiński graph over G, which ensure that χi'(SGn)=χi'(SG3). In particular, the latter result enables us to establish that χi'(SC4n)=3, χi'(SC5n)=4 and χi'(SC6n)=3 hold for any n≥ 2.