{
  "id": "1707.04910",
  "version": "v1",
  "published": "2017-07-16T16:55:16.000Z",
  "updated": "2017-07-16T16:55:16.000Z",
  "title": "Packing chromatic number versus chromatic and clique number",
  "authors": [
    "Boštjan Brešar",
    "Sandi Klavžar",
    "Douglas F. Rall",
    "Kirsti Wash"
  ],
  "comment": "17 pages, 1 table",
  "categories": [
    "math.CO"
  ],
  "abstract": "The packing chromatic number $\\chi_{\\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $i\\in [k]$, where each $V_i$ is an $i$-packing. In this paper, we investigate for a given triple $(a,b,c)$ of positive integers whether there exists a graph $G$ such that $\\omega(G) = a$, $\\chi(G) = b$, and $\\chi_{\\rho}(G) = c$. If so, we say that $(a, b, c)$ is realizable. It is proved that $b=c\\ge 3$ implies $a=b$, and that triples $(2,k,k+1)$ and $(2,k,k+2)$ are not realizable as soon as $k\\ge 4$. Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on $\\chi_{\\rho}(G)$ in terms of $\\Delta(G)$ and $\\alpha(G)$ is also proved.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-07-16T16:55:16.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "05C15",
      "05C12"
    ],
    "keywords": [
      "packing chromatic number",
      "clique number",
      "smallest integer",
      "lower bound",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}