Page 1 Next

Displaying 1 – 20 of 31

Showing per page

A decomposition of gallai multigraphs

Alexander Halperin, Colton Magnant, Kyle Pula (2014)

Discussiones Mathematicae Graph Theory

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 trees...

A note on the size Ramsey numbers for matchings versus cycles

Edy Tri Baskoro, Tomáš Vetrík (2021)

Mathematica Bohemica

For graphs G , F 1 , F 2 , we write G ( F 1 , F 2 ) if for every red-blue colouring of the edge set of G we have a red copy of F 1 or a blue copy of F 2 in G . The size Ramsey number r ^ ( F 1 , F 2 ) is the minimum number of edges of a graph G such that G ( F 1 , F 2 ) . Erdős and Faudree proved that for the cycle C n of length n and for t 2 matchings t K 2 , the size Ramsey number r ^ ( t K 2 , C n ) < n + ( 4 t + 3 ) n . We improve their upper bound for t = 2 and t = 3 by showing that r ^ ( 2 K 2 , C n ) n + 2 3 n + 9 for n 12 and r ^ ( 3 K 2 , C n ) < n + 6 n + 9 for n 25 .

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Let T s H be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H , there exist graphs G with O ( s ) edges that are Ramsey with respect to T s H .

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)

RAIRO - Theoretical Informatics and Applications

Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.

A Ramsey-style extension of a theorem of Erdős and Hajnal

Peter Komjáth (2001)

Fundamenta Mathematicae

If n, t are natural numbers, μ is an infinite cardinal, G is an n-chromatic graph of cardinality at most μ, then there is a graph X with X ( G ) ¹ μ , |X| = μ⁺, such that every subgraph of X of cardinality < t is n-colorable.

A ramsey-type theorem for multiple disjoint copies of induced subgraphs

Tomoki Nakamigawa (2014)

Discussiones Mathematicae Graph Theory

Let k and ℓ be positive integers with ℓ ≤ k − 2. It is proved that there exists a positive integer c depending on k and ℓ such that every graph of order (2k−1−ℓ/k)n+c contains n vertex disjoint induced subgraphs, where these subgraphs are isomorphic to each other and they are isomorphic to one of four graphs: (1) a clique of order k, (2) an independent set of order k, (3) the join of a clique of order ℓ and an independent set of order k − ℓ, or (4) the union of an independent set of order ℓ and...

A strongly non-Ramsey uncountable graph

Péter Komjáth (1997)

Fundamenta Mathematicae

It is consistent that there exists a graph X of cardinality 1 such that every graph has an edge coloring with 1 colors in which the induced copies of X (if there are any) are totally multicolored (get all possible colors).

Currently displaying 1 – 20 of 31

Page 1 Next