{
  "id": "1605.04267",
  "version": "v1",
  "published": "2016-05-13T17:40:02.000Z",
  "updated": "2016-05-13T17:40:02.000Z",
  "title": "$(δ, χ_{_{\\sf FF}})$-bounded families of graphs",
  "authors": [
    "Manouchehr Zaker"
  ],
  "comment": "Accepted for publication in Utilitas Mathematica",
  "categories": [
    "math.CO"
  ],
  "abstract": "For any graph $G$, the First-Fit (or Grundy) chromatic number of $G$, denoted by $\\chi_{_{\\sf FF}}(G)$, is defined as the maximum number of colors used by the First-Fit (greedy) coloring of the vertices of $G$. We call a family $\\mathcal{F}$ of graphs $(\\delta, \\chi_{_{\\sf FF}})$-bounded if there exists a function $f(x)$ with $f(x)\\rightarrow \\infty$ as $x\\rightarrow \\infty$ such that for any graph $G$ from the family one has $\\chi_{_{\\sf FF}}(G)\\geq f(\\delta(G))$, where $\\delta(G)$ is the minimum degree of $G$. We first give some results concerning $(\\delta, \\chi_{_{\\sf FF}})$-bounded families and obtain a few such families. Then we prove that for any positive integer $\\ell$, $Forb(K_{\\ell,\\ell})$ is $(\\delta, \\chi_{_{\\sf FF}})$-bounded, where $K_{\\ell,\\ell}$ is complete bipartite graph. We conjecture that if $G$ is any $C_4$-free graph then $\\chi_{_{\\sf FF}}(G)\\geq \\delta(G)+1$. We prove the validity of this conjecture for chordal graphs, complement of bipartite graphs and graphs with low minimum degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-13T17:40:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C07",
      "05C85",
      "05C38"
    ],
    "keywords": [
      "bounded families",
      "complete bipartite graph",
      "low minimum degree",
      "chromatic number",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}