Rainbow connection in graphs
From MaRDI portal
Publication:3392716
DOI10.21136/mb.2008.133947zbMath1199.05106OpenAlexW2589833411MaRDI QIDQ3392716
Ping Zhang, K. A. McKeon, Gary Chartrand, Garry L. Johns
Publication date: 17 August 2009
Full work available at URL: https://eudml.org/doc/32579
edge coloringrainbow connection numberrainbow pathrainbow coloringstrong rainbow connection numberstrong rainbow coloring
Related Items
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, Sufficient conditions for 2-rainbow connected graphs, 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, On the complexity of rainbow coloring problems, 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, Rainbow connection in 3-connected graphs, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, On the rainbow connectivity of graphs: complexity and FPT algorithms, 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, More on the colorful monochromatic connectivity, 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, 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, Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs, 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, Proper connection of graphs, Generalized rainbow connection of graphs and their complements, Properly colored paths and cycles, 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, Rainbow connection in oriented 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, Rainbow connection number and the number of blocks, Hardness and algorithms for rainbow connection, 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, Monochromatic connecting colorings in strongly connected oriented graphs, On the complexity of generalized chromatic polynomials, 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, Algorithm on rainbow connection for maximal outerplanar graphs, Rainbow connections in digraphs, Rainbow connectivity of cacti and of some infinite digraphs, Graphs with conflict-free connection number two, Rainbow paths, 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, Conflict-free connection number and independence number of a graph, Rainbow \(k\)-connectivity of random bipartite 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, Complexity results for two kinds of colored disconnections of graphs, Rainbow connection number and radius, Generalized rainbow connectivity of 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, Extremal graphs with maximum monochromatic connectivity, Vertex-monochromatic connectivity of strong digraphs, 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, (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, The rainbow connection number of the enhanced power graph of a finite group, A survey on rainbow (vertex-)index of graphs, Relations of three classes of disconnected coloring, On the inverse graph of a finite group and its rainbow connection number, Loose edge-connection of graphs, On 3-degree 4-chordal graphs, Constraining MC-numbers by the connectivity of complement graphs, Unnamed Item, On two conjectures about the proper connection number of graphs, The rainbow connectivity of cartesian product graphs, Upper bounding rainbow connection number by forest number, 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, Some results on the 3-total-rainbow index, Rainbow connection number, bridges and radius, Rainbow connection number and connected dominating sets, Strong rainbow connection numbers of toroidal meshes, Distance-local rainbow connection number, More on the rainbow disconnection in graphs, Rainbow vertex-connection number on a small-world Farey graph, Rainbow connection number and graph operations, The proper 2-connection number and size of graphs, Proper rainbow connection number of graphs, Rainbow antistrong connection in tournaments, 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, Unnamed Item, Proper connection and size of graphs, Upper bounds for the \(M D\)-numbers and characterization of extremal 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, Proper connection of direct products, Upper bounds of proper connection number of graphs, Rainbow connection numbers of Cayley graphs, Unnamed Item, The proper vertex-disconnection of graphs, On radio connection number of graphs, Two sufficient conditions for 2-connected graphs to have proper connection number 2, The conflict-free vertex-connection number and degree conditions of graphs, On the complexity of \(k\)-rainbow cycle colouring problems, Conflict-free connection number of random graphs, Minimum degree condition for proper connection number 2, The (strong) rainbow connection numbers of Cayley graphs on abelian groups, 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 and minimum degree, 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, Generalized rainbow connection of graphs, Rainbow connection number of generalized composition, Multicolorful connectivity of trees, Proper connection and proper-walk connection of digraphs, Unnamed Item, The 3-rainbow index of a graph, Graphs with 3-rainbow index \(n-1\) and \(n-2\), Unnamed Item, Unnamed Item, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, Colorful monochromatic connectivity, The complexity of determining the vertex-rainbow index of graphs, On various (strong) rainbow connection numbers of graphs, The rainbow connectivity of a graph, Rainbow trees in graphs and generalized connectivity, Total rainbow connection numbers of some special graphs, Conflict-free vertex-connections of graphs, The proper diameter of a graph, More on the minimum size of graphs with given rainbow index, (Strong) conflict-free connectivity: algorithm and complexity, Strong conflict-free connection of graphs, 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, On the (di)graphs with (directed) proper connection number two, On the (di)graphs with (directed) proper connection number two, Comparative Approach to the Multi-Valued Logic Construction for Preferences, 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, Kermit: Guided Long Read Assembly using Coloured Overlap Graphs, Kaleidoscopic edge-coloring of complete graphs and \(r\)-regular graphs, On strong proper connection number of cubic graphs, Proper connection of power graphs of finite groups, Unnamed Item, Fine-Grained Complexity of Rainbow Coloring and its Variants., 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, Some results on strong conflict-free connection number of graphs
