{
  "id": "1307.5919",
  "version": "v2",
  "published": "2013-07-23T01:17:52.000Z",
  "updated": "2016-10-20T01:52:29.000Z",
  "title": "Extremal H-colorings of graphs with fixed minimum degree",
  "authors": [
    "John Engbers"
  ],
  "comment": "26 pages, 5 figures, final version",
  "journal": "Journal of Graph Theory 79 (2015) 103-124",
  "categories": [
    "math.CO"
  ],
  "abstract": "For graphs $G$ and $H$, a homomorphism from $G$ to $H$, or $H$-coloring of $G$, is a map from the vertices of $G$ to the vertices of $H$ that preserves adjacency. When $H$ is composed of an edge with one looped endvertex, an $H$-coloring of $G$ corresponds to an independent set in $G$. Galvin showed that, for sufficiently large $n$, the complete bipartite graph $K_{\\delta,n-\\delta}$ is the $n$-vertex graph with minimum degree $\\delta$ that has the largest number of independent sets. In this paper, we begin the project of generalizing this result to arbitrary $H$. Writing $\\hom(G,H)$ for the number of $H$-colorings of $G$, we show that for fixed $H$ and $\\delta = 1$ or $\\delta = 2$, \\[ \\hom(G,H) \\leq \\max \\{\\hom(K_{\\delta+1},H)^{\\frac{n}{\\delta+1}}, \\hom(K_{\\delta,\\delta},H)^{\\frac{n}{2\\delta}}, \\hom(K_{\\delta,n-\\delta},H)\\} \\] for any $n$-vertex $G$ with minimum degree $\\delta$ (for sufficiently large $n$). We also provide examples of $H$ for which the maximum is achieved by $\\hom(K_{\\delta+1},H)^{\\frac{n}{\\delta+1}}$ and other $H$ for which the maximum is achieved by $\\hom(K_{\\delta,\\delta},H)^{\\frac{n}{2\\delta}}$. For $\\delta \\geq 3$ (and sufficiently large $n$), we provide a infinite family of $H$ for which $\\hom(G,H) \\leq \\hom(K_{\\delta,n-\\delta},H)$ for any $n$-vertex $G$ with minimum degree $\\delta$. The results generalize to weighted $H$-colorings.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-07-23T01:17:52.000Z",
      "comment": "26 pages, 6 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2016-10-20T01:52:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35"
    ],
    "keywords": [
      "fixed minimum degree",
      "extremal h-colorings",
      "sufficiently large",
      "independent set",
      "complete bipartite graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1307.5919E"
    }
  }
}