First-fit chromatic numbers of d-degenerate graphs
Journal
Discrete Mathematics
Journal Volume
312
Journal Issue
12-13
Pages
2088-2090
Date Issued
2012
Author(s)
Abstract
The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. In this short note, we first give counterexamples to some results by Balogh et al. (2008) [1], and then prove that every n-vertex d-degenerate graph has first-fit chromatic number at most log d+1dn+2. © 2012 Elsevier B.V. All rights reserved.
Type
journal article