Degenerate and star colorings of graphs on surfaces

Bojan Mohar, Simon Spacapan

We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus of graphs. As a tool we prove the following strengthening of a result of…