“Rainbow coloring”的意思、由来-开放百科全书

词条

Rainbow coloring

释义

Definitions and bounds
Exact rainbow or strong rainbow connection numbers
Complexity
Variants and generalizations
See also
Notes
References

In graph theory, a path 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 between each pair of vertices, the graph is said to be strongly rainbow-connected (or strongly rainbow colored).{{sfnp|Chartrand|Johns|McKeon|Zhang|2008}}

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 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:{{sfnp|Chartrand|Johns|McKeon|Zhang|2008}}

if and only if is a complete graph.
if and only if is a tree.

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 .{{sfnp|Ekstein|Holub|Kaiser|Koch|Camacho|Ryjáček|Schiermeyer|2013}} 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.{{sfnp|Chartrand|Johns|McKeon|Zhang|2008}}
, for each integer , and , for , where is the wheel graph.{{sfnp|Chartrand|Johns|McKeon|Zhang|2008}}

Complexity

The problem of deciding whether for a given graph is NP-complete.{{sfnp|Chakraborty|Fischer|Matsliah|Yuster|2011}} Because if and only if ,{{sfnp|Chartrand|Johns|McKeon|Zhang|2008}} it follows that deciding if is NP-complete for a given graph .

Variants and generalizations

Chartrand, Okamoto and Zhang{{sfnp|Chartrand|Okamoto|Zhang|2010}} 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.{{sfnp|Krivelevich|Yuster|2010}}

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.

Notes

References

{{citation

| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| last2 = Johns| first2 = Garry L.
| last3 = McKeon | first3 = Kathleen A.
| last4 = Zhang | first4 = Ping | author4-link = Ping Zhang (graph theorist)
| title = Rainbow connection in graphs
| journal = Mathematica Bohemica
| volume = 133 | issue = 1
| year = 2008}}.

{{citation

| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| last2 = Okamoto| first2 = Futaba
| last3 = Zhang | first3 = Ping | author3-link = Ping Zhang (graph theorist)
| title = Rainbow trees in graphs and generalized connectivity
| journal = Networks
| volume = 55 | issue = 4
| doi = 10.1002/net.20339
| year = 2010}}.

{{citation

| last1 = Chakraborty | first1 = Sourav
| last2 = Fischer | first2 = Eldar
| last3 = Matsliah | first3 = Arie
| last4 = Yuster | first4 = Raphael
| title = Hardness and algorithms for rainbow connection
| journal = Journal of Combinatorial Optimization
| volume = 21 | issue = 3 | pages = 330–347
| year = 2011
| doi = 10.1007/s10878-009-9250-9| arxiv = 0809.2493}}.

{{citation

| last1 = Krivelevich | first1 = Michael | authorlink1 = Michael Krivelevich
| last2 = Yuster | first2 = Raphael
| title = The Rainbow Connection of a Graph Is (at Most) Reciprocal to Its Minimum Degree
| journal = Journal of Graph Theory
| volume = 63 | issue = 3 | pages = 185–191
| year = 2010
| doi = 10.1002/jgt.20418}}.

{{citation

| last1 = Li | first1 = Xueliang
| last2 = Shi | first2 = Yongtang
| last3 = Sun | first3 = Yuefang
| title = Rainbow Connections of Graphs: A Survey
| journal = Graphs and Combinatorics
| volume = 29 | issue = 1 | pages = 1–38
| year = 2013
| doi = 10.1007/s00373-012-1243-2| arxiv = 1101.5747}}.

{{citation

| last1 = Li | first1 = Xueliang
| last2 = Sun | first2 = Yuefang
| title = Rainbow connections of graphs
| isbn = 978-1-4614-3119-0
| page = 103
| year = 2012
| publisher = Springer}}.

{{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}}.

1 : Graph coloring

随便看