This is the authors' abstract. We don't add key points for this paper.
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 ⌊(5 n + 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 C 4 ‐free bipartite graphs with χ FF ( G ) = k is asymptotically 2 k 2 (the upper bound answers a problem of Zaker [9]).
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Füredi et al. (2008) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: