{
  "id": "1102.5718",
  "version": "v1",
  "published": "2011-02-28T17:38:37.000Z",
  "updated": "2011-02-28T17:38:37.000Z",
  "title": "The competition number of a graph in which any two holes share at most one edge",
  "authors": [
    "Jung Yeun Lee",
    "Suh-Ryung Kim",
    "Yoshio Sano"
  ],
  "comment": "29 pages, 14 figures, 1 table",
  "categories": [
    "math.CO"
  ],
  "abstract": "The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. A hole of a graph is a cycle of length at least 4 as an induced subgraph. It holds that the competition number of a graph cannot exceed one plus the number of its holes if G satisfies a certain condition. In this paper, we show that the competition number of a graph with exactly h holes any two of which share at most one edge is at most h+1, which generalizes the existing results on this subject.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-02-28T17:38:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C75",
      "05C76"
    ],
    "keywords": [
      "competition number",
      "holes share",
      "competition graph",
      "isolated vertices",
      "important research problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1102.5718Y"
    }
  }
}