Suppose we are given graphs $B$ and $G$. In the classical Maker-Breaker game $\text{MB}(B,G)$ two players, Maker and Breaker, alternately claim edges of $B$ and it is Maker's goal to claim a copy of $G$ in $B$, while it is Breaker's goal to prevent that. In this paper, $B$ is the countably infinite complete graph $K_{\aleph_0}$ and we are given finitely many infinite subgraphs $G_1, \dots, G_k \subseteq B$. In the color preserving game, it will be Maker's goal to claim a $K_{\aleph_0} \subseteq B$, which contains infinitely many edges of each $G_i$. We present sufficient winning conditions for both Maker and Breaker, if $k>1$ and a full characterization of the game, if $k =1$. This partly answers a question of Bowler, Emde and Gut. In the (partially) pattern preserving game, it is Maker's goal to claim a copy $K$ of $K_{\aleph_0}$, such that $G_i \cap K$ is isomorphic to (a subgraph of) $G_i$ for all $i \in [k]$. In those games, we investigate some patterns for which Maker has a winning strategy.
For a tournament $T$, let $\omega(T)$ be the minimum clique number among the backedge graphs of $T$, and let $\chi(T)$ be its dichromatic number. We give a template-lifting construction. It turns a $k$-template into a regular, vertex-transitive Cayley tournament that is simultaneously $(k+1)$-$\omega$-critical and $(k+...
For graphs $F$, $G$, and $H$, we write $F \to (G, H)$ if every red/blue edge-coloring of $F$ contains either a red copy of $G$ or a blue copy of $H$. The Ramsey number $R(G, H)$ is the smallest integer $N$ such that $K_N \to (G, H)$. Let $H := K_k + nK_h$ be the generalized book graph, and let $G := K_{p+1}(a_1, a_2, \...
For a graph $G$, let $e(G)$ denote the number of edges of $G$, and let $c(G)$ be the number of distinct cycles in $G$. Morrison, Roberts and Scott asked whether, for every fixed graph $H$ and all large $n$, some $n$-vertex $H$-free graph maximizes both $e(G)$ and $c(G)$. In this paper, we show that the answer is no for...
For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with $|S|\leq k$ such that $G-S$ contains no graph of $\mathcal{F}$ as a minor. This generalizes Vertex Cover, Feedback Vertex Set, an...
Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht· 0 citations
In 2019, Sivaraman conjectured that every $P_k$-free graph has cop number at most $k-3$ for $k\geq 5$. Chudnovsky, Norin, Seymour, and Turcotte proved $P_5$-free graphs have cop number at most $2$. For $k\geq 6$ Sivaraman's conjecture remains widely open. There is little evidence to believe Sivaraman's conjecture is op...
Let $K_{j \times n}$ denote a complete multipartite graph with $j$ partite sets, each containing $n$ vertices. For given graphs $G_1$ and $G_2$, the multipartite Ramsey number (denoted $m_j(G_1, G_2)$) is the smallest integer $t$ such that any subgraph $G$ of $K_{j \times t}$ either contains a copy of $G_1$, or its com...
M. Gholami, Yaser Rowshan· Contributions to Discrete Ma...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
