On strong incidence coloring of subcubic graphs

An incidence of a graph G is a pair (u,e) where u is a vertex of G and e is an edge of G incident with u. Two incidences (u,e) and (v,f) of G are adjacent whenever (i) u = v, or (ii) e = f or (iii) uv = e or f. A strong incidence coloring of a graph G is a mapping from the set of incidences of G to the set of colors {1,& mldr;,k}, such that every two incidences that are adjacent, or adjacent to the same incidence receive distinct colors. In this paper, we prove that every connected subcubic graph G except K3,3 has a strong incidence coloring with at most 17 colors.