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 V1, V2,..., Vk so that for each 1 ≤ i < j ≤ k and for each x ∈ Vj there exists a y ∈ Vi 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 - 2008 |
Keywords
- Cartesian product
- First-fit chromatic number
- Greedy coloring
- Grundy coloring
- Grundy number
- Planar graph
- Random graph
ASJC Scopus subject areas
- General Mathematics