Incidence coloring of pseudo-Halin graphs

An incidence of a graph G is a pair (v,e) with v∈V(G), e∈E(G), such that v and e are incident. Two distinct incidences (v,e) and (w,f) are adjacent if one of the following holds: (i) v=w, or (ii) v and w are adjacent and vw∈{e,f}. An incidence coloring of a graph G is a mapping from the set of incidences to a color set such that adjacent incidences of G are assigned distinct colors. The incidence chromatic number is the minimum number of colors needed. The incidence coloring conjecture (ICC) stated that the incidence chromatic number of a graph G is at most Δ(G)+2, where Δ(G) is the maximum degree of the graph. Although the conjecture is false in general, it is valid for some classes of graphs. Maydanskiy (2005) [9] proved the ICC for any graph with Δ(G)=3. Li and Tu (2008) [7] proved that it is NP-complete to determine whether a general graph is incidence k-colorable. In this paper, we consider pseudo-Halin graphs and show that the incidence chromatic number of a 3-regular (pseudo-)Halin graph G other than W4 is 5. A pseudo-Halin graph G with Δ(G)≥4 has an incidence (Δ(G)+2)-coloring.