Sierpi ´nski图与Sierpi ´nski gasket图的条件着色∗

摘要

In this paper, the authors study r-hued coloring of Sierpi ´nski graphs and Sierpi ´nski gasket graphs, meanwhile, the authors give their r-hued chromatic number, respectively. For Sierpi´nski gasket graphs, when n > 2, χ1(Sn) =χ2(Sn)=3 andχ3(Sn)=4;if r>4, thenχr(Sn)=6. For Sierpi´nski graphs, when n>2, if 1 6 r 6 k−1, thenχr(S(n,k))=k;if r>k, thenχr(S(n,k))=k+1.%对Sierpi ´nski图与Sierpi ´nski gasket图的条件着色进行研究,分别给出其条件色数.对于Sierpi ´nski gasket图,当n>2时,χ1(Sn)=χ2(Sn)=3,χ3(Sn)=4,若r>4,则χr(Sn)=6.对于Sierpi´nski图,当n>2时,若16 r 6 k−1,则χr(S(n,k))=k；若r>k,则χr(S(n,k))=k+1.