Discussiones Mathematicae Graph Theory · 2012 · 11 citations · 9 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputational GeometryDiscrete MathematicsCartesian ProductDirected Acyclic GraphsGraph AlgorithmsGraph ColoringGraph TheoryHypergraph TheoryColoring Planar GraphsColoring TheoremsHypergraph ColoringsStrong ColoringSubgraph Isomorphism
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called �-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
9
Gary Chartrand, Garry L. Johns, Kathleen A. McKeon et al. · Mathematica Bohemica · 2008 · 567 citations · Full text
Hardness and algorithms for rainbow connection
Sourav Chakraborty, Eldar Fischer, Arie Matsliah et al. · Journal of Combinatorial Optimization · 2009 · 194 citations
Yair Caro, Arie Lev, Y. Roditty et al. · The Electronic Journal of Combinatorics · 2008 · 192 citations · Full text