Rainbow connections of graphs: a survey

From MaRDI portal

Publication:1938889

Jump to:navigation, search

DOI10.1007/s00373-012-1243-2zbMath1258.05058arXiv1101.5747MaRDI 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

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

94A60: Cryptography

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Related Items

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

Cites Work

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