On the incidence coloring number of folded hypercubes

摘要

Let (G) denote the incidence coloring number of a graph G. An easy observation shows that (G) ≥ Δ(G) + 1, where Δ(G) is the maximum degree of G. In this paper, we study the problem of incidence coloring on folded hypercubes. Since the n-dimensional folded hypercube FQ contains n-dimensional hypercube Q as a subgraph, based on a technique of Hamming codes for Q, we acquire some results of X(FQ) as follows: (1) X(FQ) = n + 2 if n = 2 - 2; (2) X(FQ) = n + 3 if n = 2 - 1; and (3) Xi(FQ) ≥ n + 3 otherwise.