Chromatic invariance conjecture for generalized Sierpiński gasket graphs

Let GG be a simple graph, let tt be a positive integer, and let S[G,t]S[G,t] denote the generalized Sierpiński gasket graph based on GG at level tt. Write χ(G)\chi(G) for the chromatic number of GG. Chromatic invariance conjecture. For each graph GG and each integer t1t\geq 1,

χ(S[G,t])=χ(G).\chi\left(S[G,t]\right)=\chi(G).

The paper proves this equality for t=1,2t=1,2, for bipartite graphs, and gives the bound χ(G)χ(S[G,t])χ(G)+1\chi(G)\leq\chi(S[G,t])\leq\chi(G)+1 for t3t\geq3; the conjecture remains open in the supplied text for arbitrary graphs and all t1t\geq1.

Sources & referencesView supporting material

Primary source

Fatemeh Attarzadeh, Ahmad Abbasi and Ali Behtoei, “Chromatic and Clique number of Generalized Sierpiński Gasket Graph S[G,t]”, arXiv:2405.19172 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.