Displaying similar documents to “Rainbow Connection Number of Dense Graphs”

Hardness Results for Total Rainbow Connection of Graphs

Lily Chen, Bofeng Huo, Yingbin Ma (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether...

On rainbow connection.

Caro, Yair, Lev, Arie, Roditty, Yehuda, Tuza, Zsolt, Yuster, Raphael (2008)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Rainbow Connection Number of Graphs with Diameter 3

Hengzhe Li, Xueliang Li, Yuefang Sun (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.

Rainbow Connection In Sparse Graphs

Arnfried Kemnitz, Jakub Przybyło, Ingo Schiermeyer, Mariusz Woźniak (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight.

Bounds for the rainbow connection number of graphs

Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-coloured graph G is rainbow-connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow-connected. In this paper we show some new bounds for the rainbow connection number of graphs depending on the minimum degree and other graph parameters. Moreover, we discuss sharpness of some of these bounds. ...

Characterizations of Graphs Having Large Proper Connection Numbers

Chira Lumduanhom, Elliot Laforge, Ping Zhang (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum...

Vertex rainbow colorings of graphs

Futaba Fujie-Okamoto, Kyle Kolasinski, Jianwei Lin, Ping Zhang (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a properly vertex-colored graph G, a path P is a rainbow path if no two vertices of P have the same color, except possibly the two end-vertices of P. If every two vertices of G are connected by a rainbow path, then G is vertex rainbow-connected. A proper vertex coloring of a connected graph G that results in a vertex rainbow-connected graph is a vertex rainbow coloring of G. The minimum number of colors needed in a vertex rainbow coloring of G is the vertex rainbow connection number...

A decomposition of gallai multigraphs

Alexander Halperin, Colton Magnant, Kyle Pula (2014)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed...

Decompositions of Plane Graphs Under Parity Constrains Given by Faces

Július Czap, Zsolt Tuza (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial...