Color Chain of a Graph

摘要

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ¶G(G){chi(G), chi_f(G), Psi_f(G), phi(G), partial Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) £ c_f(G) £ Y_f (G) £ f(G) £ ¶G(G) £ Y(G){chi (G)leq chi_f(G) leq Psi_f (G) leq phi(G) leq partial Gamma (G)leq Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ¶G(G) < Y(G){chi (G) < chi_f(G) < Psi_f (G) < phi(G) < partial Gamma (G) < Psi (G)} . The existence of such a chain was raised by Dunbar et al.