Abstract
Let G = (V, E) be a graph. A tolerance representation of G is a set
℘ = {Iv : v ∈ V} of intervals and a set t = {tv : v ∈ V} of nonnegative reals such that xy ∈ E iff Ix ∩ Iy≠ Ø and ||Ix ∩ Iy|| ≥ min {tx, ty}; in this case G is a tolerance graph. We refine this definition by saying that G is a p-tolerance graph if tv / |Iv| ≤ p for all v ∈ V.
A Grundy coloring g of G is a proper coloring of V with positive integers such that for every positive integer i, if i < g(v) then v has a neighbor u with g(u) = i. The Grundy number Γ(G) of G is the maximum integer k such that G has a Grundy coloring using k colors. It is also called the First-Fit chromatic number.
For fixed 0 ≤ p < 1 we prove that if G is a p-tolerance graph then, Γ(G) = Θ (ω(G) / (1 – p)), and in particular, Γ(G) ≤ 8 ceiling(1 / (1 – p)) ω(G). Also, we show how restricting p forbids induced copies of Ks,s. Finally, we observe that there exist 1-tolerance graphs G with ω(G) = 2 and arbitrarily large Grundy number.