Abstract. We address a problem which is a generalization of Turán-type problems recently introduced by Imolay, Karl, Nagy, and Váli. Let [Formula: see text] be a fixed graph and let [Formula: see text] be the union of [Formula: see text] edge-disjoint copies of [Formula: see text], namely [Formula: see text], where each [Formula: see text] is isomorphic to a fixed graph [Formula: see text] and [Formula: see text] for all [Formula: see text]. We call a subgraph [Formula: see text] multicolored if [Formula: see text] and [Formula: see text] share at most one edge for all [Formula: see text]. Define [Formula: see text] to be the maximum value [Formula: see text] such that there exists [Formula: see text] on [Formula: see text] vertices without a multicolored copy of [Formula: see text]. We show that [Formula: see text] and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.

Abstract. A graph [Formula: see text] is said to be [Formula: see text]-Ramsey for a [Formula: see text]-tuple of graphs [Formula: see text], denoted by [Formula: see text], if every [Formula: see text]-edge-coloring of [Formula: see text] contains a monochromatic copy of [Formula: see text] in color [Formula: see text] for some [Formula: see text]. Let [Formula: see text] denote the smallest minimum degree of [Formula: see text] over all graphs [Formula: see text] that are minimal [Formula: see text]-Ramsey for [Formula: see text] (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdős, and Lovász, who determined its value precisely for a pair of cliques. Over the past two decades the parameter [Formula: see text] has been studied by several groups of authors, their main focus being on the symmetric case, where [Formula: see text] for all [Formula: see text]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine [Formula: see text] when [Formula: see text] is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on [Formula: see text] in terms of the size of the cliques [Formula: see text], the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.

A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a “sparse” graph $G$ that is Ramsey for $H$? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously only known for the smaller class of graphs $H$ with bounded bandwidth. On the other hand, we prove that in general the treewidth of a graph $G$ that is Ramsey for $H$ cannot be bounded in terms of the treewidth of $H$ alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and $H$ is a tree.

For a tree $T$ on $n$ vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on $n$ vertices, which Maker wins as soon as the graph she builds contains a copy of $T$. We prove that if $T$ has bounded maximum degree and $n$ is sufficiently large, then Maker can win this game within $n+1$ moves. Moreover, we prove that Maker can build almost every tree on $n$ vertices in $n-1$ moves and provide nontrivial examples of families of trees which Maker cannot build in $n-1$ moves.

In this paper we study the behavior of the domination number of the Erdös--Rényi random graph $\mathcal{G}(n,p)$. Extending a result of Wieland and Godbole we show that the domination number of $\mathcal{G}(n,p)$ is equal to one of two values asymptotically almost surely whenever $p \gg \frac{\ln^2n}{\sqrt{n}}$. The explicit values are exactly at the first moment threshold, that is, where the expected number of dominating sets starts to tend to infinity. For small $p$ we also provide various nonconcentration results which indicate why some sort of lower bound on the probability $p$ is necessary in our first theorem. Concentration, though not on a constant length interval, is proven for every $p\gg 1/n$. These results show that unlike in the case of $p \gg \frac{\ln^2n}{\sqrt{n}}$, where concentration of the domination number happens around the first moment threshold, for $p = O( \ln n/n)$ it does so around the median. In particular, in this range the two are far apart from each other.