### 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},..., V_{k} so that for each 1 ≤ i < j ≤ k and for each x ∈ V_{j} there exists a y ∈ 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.

Original language | English (US) |
---|---|

Pages (from-to) | 887-900 |

Number of pages | 14 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 22 |

Issue number | 3 |

DOIs | |

State | Published - Dec 1 2008 |

### Keywords

- Cartesian product
- First-fit chromatic number
- Greedy coloring
- Grundy coloring
- Grundy number
- Planar graph
- Random graph

### ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint Dive into the research topics of 'On the first-fit chromatic number of graphs'. Together they form a unique fingerprint.

## Cite this

Balogh, J., Hartke, S. G., Liu, Q., & Yu, G. (2008). On the first-fit chromatic number of graphs.

*SIAM Journal on Discrete Mathematics*,*22*(3), 887-900. https://doi.org/10.1137/060672479