In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
in an
edge-colored graph is said to be rainbow if no color repeats on it. A graph is said to be rainbow-connected (or rainbow colored) if there is a rainbow path between each pair of its
vertices. If there is a rainbow
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between ...
between each pair of vertices, the graph is said to be strongly rainbow-connected (or strongly rainbow colored).
Definitions and bounds
The rainbow connection number of a graph
is the minimum number of colors needed to rainbow-connect
, and is denoted by
. Similarly, the strong rainbow connection number of a graph
is the minimum number of colors needed to strongly rainbow-connect
, and is denoted by
. Clearly, each strong rainbow coloring is also a rainbow coloring, while the converse is not true in general.
It is easy to observe that to rainbow-connect any connected graph
, we need at least
colors, where
is the
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
of
(i.e. the length of the longest shortest path). On the other hand, we can never use more than
colors, where
denotes the number of
edges in
. Finally, because each strongly rainbow-connected graph is rainbow-connected, we have that
.
The following are the extremal cases:
*
if and only if
is a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
.
*
if and only if
is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
.
The above shows that in terms of the number of vertices, the upper bound
is the best possible in general. In fact, a rainbow coloring using
colors can be constructed by coloring the edges of a spanning tree of
in distinct colors. The remaining uncolored edges are colored arbitrarily, without introducing new colors. When
is 2-connected, we have that
. Moreover, this is tight as witnessed by e.g. odd cycles.
Exact rainbow or strong rainbow connection numbers
The rainbow or the strong rainbow connection number has been determined for some structured graph classes:
*
, for each integer
, where
is the
cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
.
*
, for each integer
, and
, for
, where
is the
wheel graph
A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...
.
Complexity
The problem of deciding whether
for a given graph
is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
. Because
if and only if
, it follows that deciding if
is NP-complete for a given graph
.
Variants and generalizations
Chartrand, Okamoto and Zhang generalized the rainbow connection number as follows. Let
be an edge-colored nontrivial connected graph of order
. A tree
is a ''rainbow tree'' if no two edges of
are assigned the same color. Let
be a fixed integer with
. An edge coloring of
is called a ''
-rainbow coloring'' if for every set
of
vertices of
, there is a rainbow tree in
containing the vertices of
. The
-rainbow index
of
is the minimum number of colors needed in a
-rainbow coloring of
. A
-rainbow coloring using
colors is called a ''minimum
-rainbow coloring''. Thus
is the rainbow connection number of
.
Rainbow connection has also been studied in vertex-colored graphs. This concept was introduced by Krivelevich and Yuster.
Here, the rainbow vertex-connection number of a graph
, denoted by
, is the minimum number of colors needed to color
such that for each pair of vertices, there is a path connecting them whose internal vertices are assigned distinct colors.
See also
*
Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
Definition
Given an edge-colored graph , a rainbow matching in is a set of pairwise non-adja ...
Notes
References
*.
*.
*.
*.
*.
*.
*{{citation
, last1 = Ekstein , first1 = Jan
, last2 = Holub , first2 = Přemysl
, last3 = Kaiser , first3 = Tomáš
, last4 = Koch , first4 = Maria
, last5 = Camacho , first5 = Stephan Matos
, last6 = Ryjáček , first6 = Zdeněk
, last7 = Schiermeyer , first7 = Ingo
, title = The rainbow connection number of 2-connected graphs
, journal = Discrete Mathematics
, volume = 313 , issue = 19 , pages = 1884–1892
, year = 2013
, doi = 10.1016/j.disc.2012.04.022, arxiv = 1110.5736.
Graph coloring