Note on highly connected monochromatic subgraphs in 2-colored complete graphs.
Fujita, Shinya, Magnant, Colton (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Fujita, Shinya, Magnant, Colton (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
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...
Caro, Yair, Lev, Arie, Roditty, Yehuda, Tuza, Zsolt, Yuster, Raphael (2008)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
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.
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.
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. ...
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...
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...
Gyárfás, András, Ruszinkó, Miklós, Sarközy, Gábor N., Szemerédi, Endre (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Alishahi, Meysam, Taherkhani, Ali, Thomassen, Carsten (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Saenpholphat, Varaporn, Zhang, Ping (2003)
International Journal of Mathematics and Mathematical Sciences
Similarity:
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...
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...
LeSaulnier, Timothy D., Stocker, Christopher, Wenger, Paul S., West, Douglas B. (2010)
The Electronic Journal of Combinatorics [electronic only]
Similarity: