List Coloring Halin Graphs

Abstract

A Halin graph is a plane graph $H=T\cup C$, where $T$ is a tree with no vertex of degree two and at least one vertex of degree three or more, and $C$ is a cycle connecting the pendant vertices of $T$ in the cyclic order determined by the drawing of $T$. In this paper we determine the list chromatic number, the list chromatic index, and the list total chromatic number (except when $\mathrm{\Delta }=3$) of all Halin graphs, where $\mathrm{\Delta }$ denotes the maximum degree of $H$.