Source-linked AI summary
Rainbow connections of graphs -- A survey
Xueliang Li, Yuefang Sun
TL;DR
Rainbow connection strengthens graph connectivity by requiring differently colored routes, and this survey consolidates results on several rainbow parameters, algorithms, and complexity. It also records conjectures and open questions, including the behavior of strong rainbow connection and bounds across graph classes. The survey notes limitations in some reported bounds, including a tower-function constant far from the conjectured dependence on minimum degree.
Problem
The survey addresses the need to organize the growing literature on rainbow connection and related parameters, including unresolved conjectures and bounds.
Method
The paper synthesizes prior results into five categories covering rainbow parameters, algorithms, and computational complexity.
Results
The survey reports that a conjecture about attainable rainbow and strong rainbow connection values was disproved by a graph where adding one edge raises the strong requirement from six to at least seven colors.
Takeaways & Limitations
The survey provides a consolidated reference of known results, conjectures, open problems, and bounds for rainbow-connection research.
Takeaways & Limitations
A reported dense-graph bound uses a tower-function constant in 1/ε, far from the conjectured reciprocal dependence on ε.
Abstract
from arXiv · showhide
The concept of rainbow connection was introduced by Chartrand et al. in 2008. It is fairly interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow $k$-connectivity, $k$-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems or questions.
1 Introduction
The survey introduces rainbow connection as a strengthened connectivity concept modeled by edge- or vertex-colored graphs, then organizes related parameters, results, algorithms, and open questions.
- Motivation and definitions: Rainbow connection requires every vertex pair to have a path whose edges receive distinct colors.The model uses an edge-coloring of a connected graph, with adjacent edges allowed to share colors.
- Motivation and definitions: Strong rainbow connection additionally requires a rainbow shortest path, or geodesic, between every vertex pair.Its parameter satisfies diam(G) ≤ rc(G) ≤ src(G) ≤ m.
- Motivation and definitions: Rainbow k-coloring generalizes rainbow connection by requiring at least k internally disjoint rainbow paths between every pair of vertices.The parameter is motivated by the connectivity theorem guaranteeing internally disjoint paths in sufficiently connected graphs.
- Motivation and definitions: The survey also covers k-rainbow index and rainbow vertex-connection, defined through rainbow trees and distinct internal vertex colors, respectively.For vertex-connection, rvc(G) is at most n − 2, equals zero exactly for cliques, and is at least diam(G) − 1.
- Motivation and definitions: The literature is organized into five categories: (strong) rainbow connection, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection, and algorithms or computational complexity.The survey additionally records conjectures, open problems, and questions.
2 (Strong) Rainbow connection number
This section surveys basic values, relations, conjectures, counterexamples, and upper bounds for rainbow and strong rainbow connection numbers across graph classes and structural parameters.
- 2.1 Basic results: rc(G)=1 and src(G)=1 exactly for complete graphs, while rc(G)=m and src(G)=m exactly for trees.For nontrivial connected graphs, the two parameters also coincide at value 2.
- 2.1 Basic results: For cycles, rc(C_n)=src(C_n)=1 when n=3, 2 when 4≤n≤6, and 3 when n≥7.These values give a complete characterization for cycle graphs.
- 2.1 Basic results: The conjectured attainable pairs (rc(G),src(G)) were disproved: adding one edge can raise the strong rainbow requirement from six to at least seven colors.The ordinary rainbow connection number is monotone under edge addition, unlike the strong parameter.
- 2.2 Upper bounds for rainbow connection number: Minimum degree, connectivity, radius, cycles, and related structural conditions yield increasingly specialized upper bounds for rc(G).Examples include rc(G)<6 for minimum degree at least 3, rc(G)<3n/4 under a spanning cycle condition, and rc(G)≤6 for triangle-free graphs.
- 2.2 Upper bounds for rainbow connection number: Every connected n-vertex graph with minimum degree at least εn has bounded rainbow connection, with rc(G)≤C(ε).The survey reports this as a constant bound depending on ε, later describing a bound in terms of n and minimum degree.
- 2.2 Upper bounds for rainbow connection number: The survey notes that earlier bounds for dense graphs had a tower-function constant C(ε), far from the conjectured reciprocal dependence on ε.Later work resolved the associated open problem, while constants in some proofs remain nonoptimal.
- 2.2 Upper bounds for rainbow connection number: For bridgeless graphs of radius r, rc(G)≤r(r+2), and this radius-only bound is sharp for every r≥1.The same bound cannot be improved even under stronger vertex-connectivity assumptions.
G TG
The section introduces D2-trees for graphs formed from trees by adding edge-disjoint triangles, then records related strong rainbow connection results and limitations.
- G TG: A D2-tree is obtained by deleting one degree-2 vertex from each triangle, but the resulting tree need not be unique.In the example, either u1 or u2 can be deleted.
- G TG: Gt can be obtained from a tree by adding t new degree-2 vertices, and its D2-tree has m − 2t edges.
- G TG: Theorem 2.60 gives a result for graphs with m edges and t edge-disjoint triangles.
- G TG: An upper bound for strongly regular graphs is known, but its sharpness remains unresolved.
- G TG: Strong rainbow connection is harder to investigate than rainbow connection because adding edges can increase its value.
- G TG: For connected graphs with minimum degree at least ǫn, a conjecture proposes that the strong rainbow connection number is bounded.
3 Rainbow k-connectivity
Rainbow k-connectivity is difficult to determine generally, but the survey records sharp or asymptotically optimal results for complete, complete bipartite, and random graphs, alongside open problems for broader graph classes.
- For every integer k ≥2, sufficiently large complete graphs satisfy rck(Kn) = 2.
- Explicit k-colorings of sufficiently large complete graphs attain asymptotically optimal rainbow (k, 2)-connectivity, with analogous constructions for longer paths.The constructions are polynomial-time computable and use an explicit extractor in the proof.
- For every integer k ≥2, sufficiently large complete bipartite graphs satisfy rck(Kr,r) = 3, with g(k) = 2k⌈k/2⌉ sufficient.
- The survey highlights unresolved questions on complete bipartite graphs with unequal parts and on sharp upper bounds for rc2(G) in κ-connected graphs.
- For fixed d ≥2 and k = k(n) ≤O(log n), p = (log n)^(1/d)n^((d−1)/d) is a sharp threshold for rck(G(n, p)) ≤d.The proof uses many internally disjoint paths of exactly length d between every vertex pair with high probability.
4 k-rainbow index
The k-rainbow index measures the colors needed to connect every k-vertex set by a rainbow tree; the survey gives general bounds and exact values for important graph classes.
- For a connected graph of order n, rxk(G) ≤n −1 for 3 ≤k ≤n −1, while rxn(G) = n −1.Some graphs attain this upper bound.
- Every tree T of order n ≥3 satisfies rxk(T) = n −1 for every 3 ≤k ≤n.
- For a unicyclic graph of order n and girth g, the k-rainbow index is n −2 when k = 3 and g ≥4, and n −1 when g = 3 or 4 ≤k ≤n.
- Determining sharp upper bounds for rx3(G) remains an explicit problem, reflecting the difficulty of the general k-rainbow-index problem.
5 Rainbow vertex-connection number
Rainbow vertex-connection extends rainbow connectivity to vertex-colored graphs, with bounds expressed through order, minimum degree, and degree-sum conditions.
- A connected graph G with n vertices has rvc(G) < 11n.The proof uses k-strong two-step dominating sets and a probabilistic coloring argument via the Lovász Local Lemma.
- For sufficiently large n and high minimum degree δ, Li and Shi improve the bound to 3n/(δ + 1) + 5 or 4n/(δ + 1) + 5, depending on δ.
- Degree-sum bounds give rvc(G) ≤8n/(σ2 + 2) + 10 for 2 ≤σ2 ≤6 and σ2 ≥28, with related bounds for intermediate σ2 ranges.The stated intermediate-range bound uses 10n/(σ2 + 2) + A(σ2), where A(σ2) is listed explicitly.
- The degree-sum result improves the minimum-degree bound when 16 ≤δ ≤√n −1 −1, and examples show tightness up to additive factors for δ = 3, 4, 5.
6 Algorithms and computational complexity
Rainbow connectivity is computationally hard in general, but the survey also presents efficient constructions for dense, small-diameter, and random graphs.
- Deciding whether rc(G) = 2 is NP-Complete, and computing rc(G) is NP-Hard; more generally, deciding rc(G) = k is NP-complete for every fixed k ≥2.
- Checking whether a given arbitrary edge-coloring makes a graph rainbow connected is NP-Complete, with hardness obtained through the s−t rainbow-path problem.
- If minimum degree is at least εn, then rc(G) ≤C for a constant C(ε), and a corresponding coloring is constructible in polynomial time.The approach is based on a modified degree-form Szemerédi Regularity Lemma.
- For diameter-2 graphs with minimum degree at least 8log n, rc(G) ≤3, with randomized and deterministic polynomial-time coloring algorithms.
- For p = n^−ε(1±o(1)) and k ≤O(log n), a randomized polynomial-time algorithm rainbow-k-connects G(n, p) using at most one more color than optimal with probability 1−o(1).The result excludes ε > 1 because G(n,n^−ε) is almost surely disconnected there.
- The analogous rainbow vertex-connection decision problems are NP-Complete, including deciding rvc(G) = 2 and verifying a given vertex-coloring.