Abstract
The First-Fit (or Grundy) chromatic number of a graph G denoted by \(\chi _{{_\mathsf{FF}}}(G)\), 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 \(\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1\). Using this result we prove that for every \(t\ge 2\) there exists a real number \(c>0\) such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most \(cn^{1/t}\) colors. It is noted that for \(t=2\) this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balogh J, Hartke SG, Liu Q, Yu G (2008) On the first-fit chromatic number of graphs. SIAM J Discret Math 22:887–900
Bollobás B (2004) Extremal graph theory. Dover Publications Inc., New York
Bondy JA, Simonovits M (1974) Cycles of even length in graphs. J. Comb. Theory Ser B 16:97–105
Emden-Weinert T, Hougardy S, Kreuter B (1998) Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb Probab Comput 7:375–386
Füredi Z, Gyárfás A, Sárközy GN, Selkow SM (2008) Inequalities for the first-fit chromatic number. J Gr Theory 59:75–88
Gyárfás A, Lehel J (1988) On-line and first-fit coloring of graphs. J Gr Theory 12:217–227
Havet F, Sampaio L (2010) On the Grundy number of a graph. Lect Notes Comput Sci 6478:170–179
Irani S (1994) Coloring inductive graphs on-line. Algorithmica 11:53–72
Kierstead HA, Penrice SG, Trotter WT (1995) On-line first fit coloring of graphs that do not induce \(P_{5}\). SIAM J Discret Math 8(4):485–498
Kierstead HA, Trotter WT (1991) On-line graph coloring. In: McGeoch LA, Sleator DD (eds) On-line algorithms: Proceedings of DIMACS workshop, Feb 11–13, 1991. American Mathematical Society 1992, pp 85–92
Kortsarz G (2007) A lower bound for approximating Grundy number. Discret Math Theory Comput Sci 9:7–21
Maffray F, Preissmann M (1996) On the \(NP\)-completeness of the \(k\)-colorability problem for triangle-free graphs. Discret Math 162:313–317
Spencer J (1977) Asymptotic lower bounds for Ramsey functions. Discret Math 20:69–76
Zaker M (2005) Grundy chromatic number of the complement of bipartite graphs. Australas J Comb 31:325–329
Zaker M (2006) Results on the Grundy chromatic number of graphs. Discret Math 306:3166–3173
Zaker M (2007) Inequalities for the Grundy chromatic number of graphs. Discret Appl Math 155:2567–2572
Zaker M (2009) Some colorful results for graphs without an even cycle, SBU Combinatorics Day, March 4, 2009. Shahid Beheshti University, Tehran
Zaker M (2009) On the first-fit coloring of graphs, In: Proccedings of international conference on discrete mathematics, algebra and their applications (DIMA09), Oct 19–22, 2009. Minsk, Belarus
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zaker, M., Soltani, H. First-Fit colorings of graphs with no cycles of a prescribed even length. J Comb Optim 32, 775–783 (2016). https://doi.org/10.1007/s10878-015-9900-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9900-z