Inequalities for the first‐fit chromatic number |
| |
| Authors: | Zoltán Füredi András Gyárfás Gábor N Sárközy Stanley Selkow |
| |
| Institution: | 1. Alfréd Rényi Institute 96, Hungarian Academy of Sciences, Budapest H‐1364, P.O. Box 127, Hungary;2. Department of Mathematics, University of Illinois at Urbana‐Champaign, Urbana, Illinois 61801;3. Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest H‐1518, P.O. Box 63, Hungary;4. Computer Science Department, Worcester Polytechnic Institute, Worcester, Massachusetts 01609 |
| |
| Abstract: | The First‐Fit (or Grundy) chromatic number of G, written as χFF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C4‐free bipartite graphs with χFF(G) = k is asymptotically 2k2 (the upper bound answers a problem of Zaker 9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008 |
| |
| Keywords: | graphs chromatic number greedy algorithm difference |
|
|
