Rainbow connections of graphs: a survey

From MaRDI portal

Publication:1938889

Jump to:navigation, search

DOI10.1007/s00373-012-1243-2zbMath1258.05058arXiv1101.5747OpenAlexW2034743574MaRDI QIDQ1938889

Yuefang Sun, Yongtang Shi, Xue Liang Li

Publication date: 25 February 2013

Published in: Graphs and Combinatorics, SpringerBriefs in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.5747

zbMATH Keywords

computational complexity rainbow connection number rainbow connectivity \(k\)-rainbow index rainbow path rainbow vertex-connection number rainbow \(k\)-connectivity strong rainbow connection number secure transfer of information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

On two conjectures about the proper connection number of graphs, Total monochromatic connection of graphs, The rainbow connection number of the power graph of a finite group, Rainbow Connection of Random Regular Graphs, On the Fine-Grained Complexity of Rainbow Coloring, Rainbow connection number of comb product of graphs, Strong rainbow connection numbers of toroidal meshes, Rainbow vertex-connection number on a small-world Farey graph, Rainbow connection number and graph operations, Proper rainbow connection number of graphs, Rainbow antistrong connection in tournaments, Proper connection number of bipartite graphs, A note on the rainbow connection of random regular graphs, The strong 3-rainbow index of edge-comb product of a path and a connected graph, Proper connection and size of graphs, Graphs with small total rainbow connection number, The monochromatic connectivity of graphs, The strong 3-rainbow index of some certain graphs and its amalgamation, 3-rainbow index and forbidden subgraphs, Upper bounds of proper connection number of graphs, Rainbow connection numbers of Cayley graphs, Unnamed Item, The conflict-free vertex-connection number and degree conditions of graphs, (Strong) rainbow connection on the splitting of 3-path, An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs, Rainbow connectivity and rainbow index of inhomogeneous random graphs, (1, 2)-rainbow connection number at most 3 in connected dense graphs, (Strong) proper vertex connection of some digraphs, On the complexity of \(k\)-rainbow cycle colouring problems, Long rainbow paths and rainbow cycles in edge colored graphs. A survey, Minimum degree condition for proper connection number 2, A survey on rainbow (vertex-)index of graphs, Loose edge-connection of graphs, On 3-degree 4-chordal graphs, Concentration of rainbow \(k\)-connectivity of a multiplex random graph, Hardness results for three kinds of colored connections of graphs, Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\), Monochromatic disconnection of graphs, Upper bound involving parameter \(\sigma_2\) for the rainbow connection number, Rainbow vertex \(k\)-connection in graphs, Rainbow connection for some families of hypergraphs, On proper (strong) rainbow connection of graphs, The vertex-rainbow connection number of some graph operations, Conflict-free vertex connection number at most 3 and size of graphs, Rainbow and strong rainbow connection number for some families of graphs, Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, Template-driven rainbow coloring of proper interval graphs, Generalized rainbow connection of graphs, Rainbow connection number of generalized composition, Multicolorful connectivity of trees, Proper connection and proper-walk connection of digraphs, Rainbow vertex-connection and graph products, The 3-rainbow index of a graph, Graphs with 3-rainbow index \(n-1\) and \(n-2\), Unnamed Item, Template-driven rainbow coloring of proper interval graphs, On the total proper connection of graphs, 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, More on the minimum size of graphs with given rainbow index, (Strong) conflict-free connectivity: algorithm and complexity, Monochromatic connectivity and graph products, Rainbow 2-connection numbers of Cayley graphs, On the threshold for rainbow connection number \(r\) in random graphs, The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths, Solutions to conjectures on the (k ,ℓ)-rainbow index of complete graphs, The strong 3-rainbow index of edge-amalgamation of some graphs, Rainbow connectivity of the non-commuting graph of a finite group, Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph, Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes, Kaleidoscopic edge-coloring of complete graphs and \(r\)-regular graphs, Facial rainbow coloring of plane graphs, Unnamed Item, Fine-Grained Complexity of Rainbow Coloring and its Variants., Pattern Colored Hamilton Cycles in Random Graphs, Highly Irregular, Rainbow connectivity using a rank genetic algorithm: Moore cages with girth six, Rainbow perfect domination in lattice graphs, Color code techniques in rainbow connection, Graphs with 4-rainbow index 3 and \(n-1\), Rainbow connection and forbidden subgraphs, $(g,f)$-Chromatic spanning trees and forests, Note on the hardness of rainbow connections for planar and line graphs, The 3-rainbow index and connected dominating sets, Algorithms for the rainbow vertex coloring problem on graph classes, Hardness results for total rainbow connection of graphs, Characterizations of graphs having large proper connection numbers, 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, Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs, Upper bounding rainbow connection number by forest number, Some results on the 3-total-rainbow index, The rainbow vertex-index of complementary graphs, The \((k,\ell)\)-rainbow index for complete bipartite and multipartite graphs, Total rainbow connection number and complementary graph, Rainbow connection number of amalgamation of some graphs, Some remarks on rainbow connectivity, Upper bounds for the total rainbow connection of graphs, On the complexity of rainbow coloring problems, Note on vertex and total proper connection numbers, Distance-local rainbow connection number, More on the rainbow disconnection in graphs, Rainbow connection number and independence number of a graph, Rainbow colouring of split graphs, Conflict-free connections of graphs, Rainbow disconnection in graphs, Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number, Injective coloring of some graph operations, The proper 2-connection number and size of graphs, Rainbow connection in 3-connected graphs, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, More on the colorful monochromatic connectivity, A note on the minimum size of \(k\)-rainbow-connected graphs, Two sufficient conditions for 2-connected graphs to have proper connection number 2, Tight upper bound of the rainbow vertex-connection number for 2-connected graphs, Total rainbow \(k\)-connection in graphs, Rainbow connection of graphs with diameter 2, Conflict-free connection number of random graphs, Proper connection number and connected dominating sets, Rainbow connections of graphs: a survey, Rainbow vertex-connection and forbidden subgraphs, Total rainbow connection of digraphs, Proper connection number of random graphs, Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2, On (strong) proper vertex-connection of graphs, Rainbow vertex connection of digraphs, Strong rainbow connection in digraphs, Further hardness results on rainbow and strong rainbow connectivity, Generalized rainbow connection of graphs and their complements, Nordhaus-Gaddum-type theorem for total-proper connection number of graphs, Some upper bounds for the 3-proper index of graphs, Proper connection number of graph products, On conflict-free connection of graphs, Rainbow connection in oriented graphs, On forbidden subgraphs and rainbow connection in graphs with minimum degree 2, Note on the perfect EIC-graphs, 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, Rainbow connection number and the number of blocks, Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs, The generalized 3-connectivity of star graphs and bubble-sort graphs, Coupon coloring of cographs, On rainbow total-coloring of a graph, 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, Rainbow connection number of graphs with diameter 3, Complexity of rainbow vertex connectivity problems for restricted graph classes, Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks, Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs, Erdős-Gallai-type results for colorful monochromatic connectivity of a graph, Coupon coloring of some special graphs, Rainbow connections in digraphs, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, Graphs with conflict-free connection number two, Minimum degree and size conditions for the proper connection number of graphs, The (vertex-)monochromatic index of a graph, Rainbow connection and graph products, Some results on the 3-vertex-rainbow index of a graph, Rainbow \(k\)-connectivity of random bipartite graphs, The \((k,\ell )\)-proper index of graphs, Proper connection numbers of complementary graphs, The vertex-rainbow index of a graph, Odd connection and odd vertex-connection of graphs, Rainbow connectivity of Moore cages of girth 6, (Strong) total proper connection of some digraphs, Note on minimally \(d\)-rainbow connected graphs, Note on the vertex-rainbow index of a graph, Fine-grained complexity of rainbow coloring and its variants, From colourful to rainbow paths in graphs: colouring the vertices, Conflict-free connection number and size of graphs, Conflict-free connection of trees, Extremal graphs with maximum monochromatic connectivity, Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs, Rainbow and monochromatic vertex-connection of random graphs, Rainbow connectivity and rainbow criticality on graph classes, Bounds for the rainbow disconnection numbers of graphs, The \((k,\ell)\)-rainbow index of random graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1938889&oldid=34058770"