{
  "id": "1602.00922",
  "version": "v1",
  "published": "2016-02-02T13:52:00.000Z",
  "updated": "2016-02-02T13:52:00.000Z",
  "title": "Rainbow vertex-connection and forbidden subgraphs",
  "authors": [
    "Wenjing Li",
    "Xueliang Li",
    "Jingshu Zhang"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A path in a vertex-colored graph is called \\emph{vertex-rainbow} if its internal vertices have pairwise distinct colors. A graph $G$ is \\emph{rainbow vertex-connected} if for any two distinct vertices of $G$, there is a vertex-rainbow path connecting them. For a connected graph $G$, the \\emph{rainbow vertex-connection number} of $G$, denoted by $rvc(G)$, is defined as the minimum number of colors that are required to make $G$ rainbow vertex-connected. In this paper, we find all the families $\\mathcal{F}$ of connected graphs with $|\\mathcal{F}|\\in\\{1,2\\}$, for which there is a constant $k_\\mathcal{F}$ such that, for every connected $\\mathcal{F}$-free graph $G$, $rvc(G)\\leq diam(G)+k_\\mathcal{F}$, where $diam(G)$ is the diameter of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-02T13:52:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C38",
      "05C40"
    ],
    "keywords": [
      "forbidden subgraphs",
      "rainbow vertex-connection",
      "connected graph",
      "minimum number",
      "internal vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160200922L"
    }
  }
}