The Linear t-Colorings of Sierpi ński-Like Graphs

摘要

A proper t-coloring of a graph G is a mapping φ: V(G) → [1, t] such that φ(u) ≠ φ(v) if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by χ(G), is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by lc(G), is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), S~+(n, k) and S~(++)(n, k) are studied. It is obtained that lc(S(n, k)) = χ(S(n, k)) = k for any positive integers n and k, lc(S~+ (n, k)) = χ(S~+ (n, k)) = k and lc(S~(++) (n, k)) = χ(S~(++) (n, k)) = k for any positive integers n ≥ 2 and k ≥ 3. Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.