For a graph $H$ with $3\mid e(H)$, the zero-sum Ramsey number $R(H,\Z_3)$ is the least integer $N$ such that every labeling of the edges of $K_N$ by elements of $\Z_3$ contains a copy of $H$ whose edge labels sum to zero. We determine the last previously unresolved infinite family in the complete-graph case modulo $3$. More precisely, we prove that \(R(K_n,\Z_3)=n+3\) for every $n\ge 10$ satisfying $n\equiv 1\pmod 3$. Consequently, for $k\ge 1$, \(R(K_{9k+7},\Z_3)=9k+10\), resolving a problem of Caro and Mifsud.
Let $K_N^{(r)}$ denote the $N$-vertex complete $r$-uniform hypergraph. For an $r$-uniform hypergraph $H$ and an integer $k\geq2$, the $k$-color Ramsey number $R(H,k)$ is the least integer $N$ such that every $k$-edge-coloring of $K_N^{(r)}$ contains a monochromatic copy of $H$. When $k\mid\esize(H)$, the zero-sum Ramse...
For graphs $G$ and $H$, let $\mathbf N(G,H)$ denote the number of unlabeled, not necessarily induced copies of $H$ in $G$, and let $\mathbf N_{\mathcal P}(n,H)$ be the maximum of $\mathbf N(G,H)$ over all $n$-vertex planar graphs $G$. We prove that, for every fixed integer $m\geq 3$, $$\mathbf N_{\mathcal P}(n,C_{2m+1}...
For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph an...
For a graph $H$ and a family of graphs $\mathcal F$, let $\text{ex}(n,H,\mathcal F)$ denote the maximum number of copies of $H$ in an $\mathcal F$-free graph on $n$ vertices. For every integer $i\ge 3$, let $C_i$ denote the cycle of length $i$. For $r\ge 3$, set $\mathscr {C}_r=\{C_3,C_4,\ldots,C_r\},$ and set $\mathsc...
For a simple graph $G$ with $n$ vertices, write its chromatic polynomial in the rising factorial basis as $$ \chi_G(x)=\sum_{i=0}^{n}(-1)^{n-i}c_i(G)\langle x\rangle_i,$$ where $ \langle x\rangle_i=x(x+1)\cdots(x+i-1).$ The associated $\tau$-polynomial $$ \tau_G(x)=\sum_{i=0}^{n}c_i(G)x^i $$ was defined and systematica...
Ming-Yang Kang, Zhi-Xin Liu, Sophie C. C. Sun et al.· 0 citations
For $1\le s<t$ and any graph $G$, the weakened Gallai-Ramsey number $gr^t_s(G)$ is defined to be the least $p\in \mathbb{N}$ such that every Gallai $t$-coloring of the edges of $K_p$ (i.e., a $t$-coloring that lacks rainbow triangles) contains a subgraph isomorphic to $G$ whose edges use at most $s$ of the colors. In t...
M. Budden, A. Gregory· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
