On the First-Fit Chromatic Number of Graphs

Source abstract

The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. It is also called the Grundy number, which is defined to be the maximum number of classes in an ordered partition of the vertex set of a graph G into independent sets $V_1, V_2, \dots, V_k$ so that for each $1\le i<j\le k$ and for each $x\in V_j$ there exists a $y\in V_i$ such that x and y are adjacent. In this paper, we study the first-fit chromatic number of outerplanar and planar graphs as well as Cartesian products of graphs, and in particular we give asymptotically tight results for outerplanar graphs.