{
  "id": "1610.05616",
  "version": "v1",
  "published": "2016-10-18T13:49:28.000Z",
  "updated": "2016-10-18T13:49:28.000Z",
  "title": "3-Rainbow index and forbidden subgraphs",
  "authors": [
    "Wenjing Li",
    "Xueliang Li",
    "Jingshu Zhang"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A tree in an edge-colored connected graph $G$ is called \\emph{a rainbow tree} if no two edges of it are assigned the same color. For a vertex subset $S\\subseteq V(G)$, a tree is called an \\emph{$S$-tree} if it connects $S$ in $G$. A \\emph{$k$-rainbow coloring} of $G$ is an edge-coloring of $G$ having the property that for every set $S$ of $k$ vertices of $G$, there exists a rainbow $S$-tree in $G$. The minimum number of colors that are needed in a $k$-rainbow coloring of $G$ is the \\emph{$k$-rainbow index} of $G$, denoted by $rx_k(G)$. The \\emph{Steiner distance $d(S)$} of a set $S$ of vertices of $G$ is the minimum size of an $S$-tree $T$. The \\emph{$k$-Steiner diameter $sdiam_k(G)$} of $G$ is defined as the maximum Steiner distance of $S$ among all sets $S$ with $k$ vertices of $G$. In this paper, we focus on the 3-rainbow index of graphs and find all families $\\mathcal{F}$ of connected graphs, for which there is a constant $C_\\mathcal{F}$ such that, for every connected $\\mathcal{F}$-free graph $G$, $rx_3(G)\\leq sdiam_3(G)+C_\\mathcal{F}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-18T13:49:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C38",
      "05C40"
    ],
    "keywords": [
      "forbidden subgraphs",
      "connected graph",
      "maximum steiner distance",
      "free graph",
      "rainbow coloring"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}