The rainbow connection of a graph is (at most) reciprocal to its minimum degree
From MaRDI portal
Publication:5190328
DOI10.1002/jgt.20418zbMath1193.05079OpenAlexW4233791220WikidataQ105815972 ScholiaQ105815972MaRDI QIDQ5190328
Raphael Yuster, Michael Krivelevich
Publication date: 15 March 2010
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20418
Related Items (99)
On finding rainbow and colorful paths ⋮ Algorithms for the rainbow vertex coloring problem on graph classes ⋮ Hardness results for total rainbow connection of graphs ⋮ Rainbow connections for outerplanar graphs with diameter 2 and 3 ⋮ The rainbow vertex-disconnection in graphs ⋮ Some results on the total proper \(k\)-connection number ⋮ Finite families of forbidden subgraphs for rainbow connection in graphs ⋮ Note on the upper bound of the rainbow index of a graph ⋮ Sufficient conditions for 2-rainbow connected graphs ⋮ Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs ⋮ Upper bounding rainbow connection number by forest number ⋮ Rainbow Connection of Random Regular Graphs ⋮ Some results on the 3-total-rainbow index ⋮ The rainbow vertex-index of complementary graphs ⋮ Total rainbow connection number and complementary graph ⋮ Rainbow connection number, bridges and radius ⋮ Rainbow connection number and connected dominating sets ⋮ Some remarks on rainbow connectivity ⋮ Upper bounds for the total rainbow connection of graphs ⋮ On the complexity of rainbow coloring problems ⋮ Distance-local rainbow connection number ⋮ Rainbow connection number and independence number of a graph ⋮ Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number ⋮ Rainbow vertex-connection number on a small-world Farey graph ⋮ Rainbow antistrong connection in tournaments ⋮ Rainbow connection in 3-connected graphs ⋮ Graphs with small total rainbow connection number ⋮ On the rainbow connectivity of graphs: complexity and FPT algorithms ⋮ Rainbow connection numbers of Cayley graphs ⋮ The rainbow connection number of 2-connected graphs ⋮ Further hardness results on the rainbow vertex-connection number of graphs ⋮ Upper bounds for the rainbow connection numbers of line graphs ⋮ On radio connection number of graphs ⋮ Tight upper bound of the rainbow vertex-connection number for 2-connected graphs ⋮ Total rainbow \(k\)-connection in graphs ⋮ The conflict-free vertex-connection number and degree conditions of graphs ⋮ An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs ⋮ Rainbow connection of graphs with diameter 2 ⋮ On the complexity of \(k\)-rainbow cycle colouring problems ⋮ Rainbow connections of graphs: a survey ⋮ Rainbow vertex-connection and forbidden subgraphs ⋮ Total rainbow connection of digraphs ⋮ Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2 ⋮ A survey on rainbow (vertex-)index of graphs ⋮ On (strong) proper vertex-connection of graphs ⋮ Relations of three classes of disconnected coloring ⋮ Rainbow vertex connection of digraphs ⋮ Constraining MC-numbers by the connectivity of complement graphs ⋮ The (strong) rainbow connection numbers of Cayley graphs on abelian groups ⋮ Strong rainbow connection in digraphs ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ On rainbow-\(k\)-connectivity of random graphs ⋮ The complexity of determining the rainbow vertex-connection of a graph ⋮ Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\) ⋮ Proper connection of graphs ⋮ Generalized rainbow connection of graphs and their complements ⋮ Unnamed Item ⋮ Rainbow vertex \(k\)-connection in graphs ⋮ Rainbow connection and minimum degree ⋮ Rainbow connection for some families of hypergraphs ⋮ Rainbow connection in oriented graphs ⋮ The vertex-rainbow connection number of some graph operations ⋮ Conflict-free vertex connection number at most 3 and size of graphs ⋮ On forbidden subgraphs and rainbow connection in graphs with minimum degree 2 ⋮ The \(k\)-proper index of graphs ⋮ Hardness result for the total rainbow \(k\)-connection of graphs ⋮ Rainbow connection number of graph power and graph products ⋮ On rainbow total-coloring of a graph ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Rainbow connection numbers of Cayley digraphs on abelian groups ⋮ On total rainbow \(k\)-connected graphs ⋮ Graphs with vertex rainbow connection number two ⋮ Rainbow connection in some digraphs ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Multicolorful connectivity of trees ⋮ Erdős-Gallai-type results for colorful monochromatic connectivity of a graph ⋮ Rainbow connections in digraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The (vertex-)monochromatic index of a graph ⋮ Rainbow connection and graph products ⋮ Some results on the 3-vertex-rainbow index of a graph ⋮ Colorful monochromatic connectivity ⋮ The complexity of determining the vertex-rainbow index of graphs ⋮ On various (strong) rainbow connection numbers of graphs ⋮ Total rainbow connection numbers of some special graphs ⋮ Conflict-free vertex-connections of graphs ⋮ The vertex-rainbow index of a graph ⋮ (Strong) total proper connection of some digraphs ⋮ Rainbow connection number and radius ⋮ Generalized rainbow connectivity of graphs ⋮ Note on the vertex-rainbow index of a graph ⋮ From colourful to rainbow paths in graphs: colouring the vertices ⋮ Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes ⋮ Rainbow and monochromatic vertex-connection of random graphs ⋮ Rainbow perfect domination in lattice graphs ⋮ Rainbow connection and forbidden subgraphs ⋮ Note on the hardness of rainbow connections for planar and line graphs ⋮ The \((k,\ell)\)-rainbow index of random graphs
Cites Work
This page was built for publication: The rainbow connection of a graph is (at most) reciprocal to its minimum degree
