First-Fit colorings of graphs with no cycles of a prescribed even length |
| |
Authors: | Email author" target="_blank">Manouchehr?ZakerEmail author Hossein?Soltani |
| |
Institution: | 1.Department of Mathematics,Institute for Advanced Studies in Basic Sciences,Zanjan,Iran |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |