{
  "id": "1711.08261",
  "version": "v1",
  "published": "2017-11-22T13:02:47.000Z",
  "updated": "2017-11-22T13:02:47.000Z",
  "title": "A sufficient condition of a graph with boxicity at most its chromatic number",
  "authors": [
    "Akira Kamibeppu"
  ],
  "comment": "7 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A box in Euclidean $k$-space is the Cartesian product of $k$ closed intervals on the real line. The boxicity of a graph $G$, denoted by $\\text{box}(G)$, is the minimum nonnegative integer $k$ such that $G$ can be isomorphic to the intersection graph of a family of boxes in Euclidean $k$-space. In this paper, we present a sufficient condition of a graph under which $\\text{box}(G)\\leq \\chi (G)$ holds, where $\\chi (G)$ denotes the chromatic number of $G$. Bhowmick and Chandran (2010) proved that $\\text{box}(G)\\leq \\chi (G)$ holds for an asteroidal triple free graph. We give an example of a family of graphs with an asteroidal triple each of which satisfies $\\text{box}(G)\\leq \\chi (G)$. This also contributes the conjecture $\\text{box}(G)=O(\\Delta_G)$ mentioned by Chandran et al. (2008) from the viewpoint of making the graphs clear, where $\\Delta_G$ is the maximum degree of a graph $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-22T13:02:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C62"
    ],
    "keywords": [
      "sufficient condition",
      "chromatic number",
      "asteroidal triple free graph",
      "cartesian product",
      "graphs clear"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}