3-rainbow index and forbidden subgraphs

DOI10.1007/S00373-017-1783-6MaRDI QIDQ2409535zbMATH OpenOpenAlexFDO

Authors Wenjing Li, Jingshu Zhang, Xueliang Li

Publication date 11 October 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.05616

zbMATH Keywords

3-rainbow index\(k\)-rainbow indexforbidden subgraphsrainbow tree

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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 $SsubseteqV(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 $r{x}_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 $sdia{m}_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 finite families $mathcalF$ of connected graphs, for which there is a constant $C_{m}athcalF$ such that, for every connected $mathcalF$-free graph $G$, $r{x}_3(G)leqsdia{m}_3(G)+C_{m}athcalF$.

Recommendations

• The 3-rainbow index of a graph
• Graphs with 3-rainbow index \(n-1\) and \(n-2\)
• Some results on the 3-vertex-rainbow index of a graph
• scientific article; zbMATH DE number 6761154
• The 3-rainbow index and connected dominating sets

Cites work

• Finite families of forbidden subgraphs for rainbow connection in graphs
• Graph theory with applications
• Rainbow connection and forbidden subgraphs
• Rainbow connection in graphs
• Rainbow trees in graphs and generalized connectivity
• Rainbow vertex-connection and forbidden subgraphs
• The 3-rainbow index and connected dominating sets
• The 3-rainbow index of a graph

Cited in

(6)

• The 3-rainbow index of a graph
• The 3-rainbow index and connected dominating sets
• 3-colourability and forbidden subgraphs
• Some upper bounds for the 3-rainbow index of line graphs.
• The strong 3-rainbow index of edge-amalgamation of some graphs
• Total-rainbow connection and forbidden subgraphs

This page was built for publication: 3-rainbow index and forbidden subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409535)