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 v w ∈ { 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 W 4 is 5. A pseudo-Halin graph G with Δ ( G ) ≥ 4 has an incidence ( Δ ( G ) + 2 ) -coloring.