{
  "id": "1508.06454",
  "version": "v1",
  "published": "2015-08-26T11:52:47.000Z",
  "updated": "2015-08-26T11:52:47.000Z",
  "title": "Universal targets for homomorphisms of edge-colored graphs",
  "authors": [
    "Grzegorz Guśpiel",
    "Grzegorz Gutowski"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A $k$-edge-colored graph is a finite, simple graph with edges labeled by numbers $1,\\ldots,k$. A function from the vertex set of one $k$-edge-colored graph to another is a homomorphism if the color of every edge is preserved over the mapping. Given a class of graphs $\\mathcal{F}$, a $k$-edge-colored graph $\\mathbb{H}$ (not necessarily with the underlying graph in $\\mathcal{F}$) is $k$-universal for $\\mathcal{F}$ when any $k$-edge-colored graph with the underlying graph in $\\mathcal{F}$ maps homomorphically to $\\mathbb{H}$. We characterize graph classes that admit $k$-universal graphs. For such classes, we establish asymptotically almost tight bounds on the size of the smallest universal graph. The main results are the following. A class of graphs $\\mathcal{F}$ admits $k$-universal graphs for $k\\geq2$ if and only if there is an absolute constant that bounds the acyclic chromatic number of any graph in $\\mathcal{F}$. For any such class, the size of the smallest $k$-universal graph is $\\Omega\\left(k^{D(\\mathcal{F})}\\right)$ and $O\\left(k^{\\left\\lceil D(\\mathcal{F})\\right\\rceil}\\right)$, where $D(\\mathcal{F})$ is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of all graphs in $\\mathcal{F}$. A connection between the acyclic coloring and the existence of universal graphs was first observed by Alon and Marshall (Journal of Algebraic Combinatorics, 8(1):5-13, 1998). One of their results is that for the class of planar graphs, the size of the smallest $k$-universal graph is between $k^3+3$ and $5k^4$. Our results yield that this size is $\\Theta\\left(k^3\\right)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-26T11:52:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C60",
      "G.2.2"
    ],
    "keywords": [
      "edge-colored graph",
      "universal targets",
      "homomorphism",
      "smallest universal graph",
      "acyclic chromatic number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150806454G"
    }
  }
}