### A bound for size Ramsey numbers of multipartite graphs.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

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

We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.

For graphs $G$, ${F}_{1}$, ${F}_{2}$, we write $G\to ({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 $\widehat{r}({F}_{1},{F}_{2})$ is the minimum number of edges of a graph $G$ such that $G\to ({F}_{1},{F}_{2})$. Erdős and Faudree proved that for the cycle ${C}_{n}$ of length $n$ and for $t\ge 2$ matchings $t{K}_{2}$, the size Ramsey number $\widehat{r}(t{K}_{2},{C}_{n})<n+(4t+3)\sqrt{n}$. We improve their upper bound for $t=2$ and $t=3$ by showing that $\widehat{r}(2{K}_{2},{C}_{n})\le n+2\sqrt{3n}+9$ for $n\ge 12$ and $\widehat{r}(3{K}_{2},{C}_{n})<n+6\sqrt{n}+9$ for $n\ge 25$.

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\left(s\right)$ edges that are Ramsey with respect to ${T}_{s}H$.

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.

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\to \left(G\right){\xb9}_{\mu}$, |X| = μ⁺, such that every subgraph of X of cardinality < t is n-colorable.

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

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