On the complete chromatic number of Halin graphs (Q1363017)

The complete chromatic number of a plane graph \(G\) is the minimal number \(k\) such that all elements of \(G\) (vertices, edges, and faces) can be coloured with at most \(k\) colours in such a way that any two adjacent or incident elements have different colours. A Halin graph is a planar graph of minimal degree at least 3 which can be obtained from a tree by adding a cycle whose vertex set is the set of all endvertices of the tree. The authors show that the complete chromatic number of a Halin graph equals its maximal degree plus 1 if that maximal degree is at least 6. Their proof consists of an extensive case analysis.