First-Fit colorings of graphs with no cycles of a prescribed even length

摘要

The First-Fit (or Grundy) chromatic number of a graph G denoted by , is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number . Using this result we prove that for every there exists a real number such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most colors. It is noted that for this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.