Some Combinatorial Problems on Halin Graphs

Let $T$ be a tree with no degree 2 vertices and $L(T)={l_1,\ldots,l_r}, r \geq 2$denotethesetofleavesin$T$\mathrm{.}AnHalingraph$G$ is a graph obtained from $T$ such that $V(G)=V(T)$ and $E(G)=E(T) \cup {{l_i,l_{i+1}} ~|~ 1 \leq i \leq r-1} \cup {l_1,l_r}$. In this paper, we investigate combinatorial problems such as, testing whether a given graph is Halin or not, chromatic bounds, an algorithm to color Halin graphs with the minimum number of colors. Further, we present polynomial-time algorithms for testing and coloring problems.