A Coloring Problem (Q3983387)

Given a totally ordered set of colours, the greedy algorithm for colouring the vertices of a graph assigns to each vertex of the graph (in some order) the least colour not already used at an adjacent vertex. When applied to a path on \(n\geq 2\) vertices, the algorithm uses either 2 or 3 colours, depending on the order in which the vertices are taken. The problem of counting the number of vertex orderings for a path on \(n\) vertices (out of the \(n!\) possible orderings) for which the greedy algorithm uses only two colours was solved by \textit{I. Bouwer} and \textit{Z. Star} [Am. Math. Mon. 95, No. 2, 118-121 (1988; Zbl 0735.05037)] in terms of exponential generating functions obtained by solving certain differential equations. The present paper offers a direct combinatorial way to obtain the generating functions of Bouwer and Star.