A linear upper bound on the $\mathbb{Z}_p$-Ramsey number of graphs with sufficiently large $2$-packing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914585224675328 |
|---|---|
| author | Heath, Emily Simmons, Andrew |
| author_facet | Heath, Emily Simmons, Andrew |
| contents | Given a positive integer $k$ and graph $G$, the $\mathbb{Z}_k$-Ramsey number $R(G,\mathbb{Z}_k)$ is the least $N$ (if it exists) such that every coloring $f:E(K_N)\rightarrow \mathbb{Z}_k$ contains a copy $G'$ of $G$ such that $\sum_{e\in E(G')}f(e)=0$. Motivated by a question of Caro and Mifsud, we study the $\mathbb{Z}_k$-Ramsey number of graphs with a sufficiently large 2-packing, i.e. a set of vertices $S\subseteq V(G)$ such that $N[u]\cap N[v]=\emptyset$ for all distinct $u,v\in S$. In particular, we prove that $R(G,\mathbb{Z}_p)\leq n+6p-9$ for all $n$-vertex graphs $G$ and all primes $p$ such that $p$ divides $e(G)$, the minimum degree of $G$ is at least $1$, and there exists a $2$-packing of $G$ with size $p-1$. This upper bound improves depending on vertex degrees in the $2$-packing, with equality in certain cases. The result also implies an upper bound of the form $R(G,\mathbb{Z}_p)\leq n+C$ for $n$-vertex graphs $G$ of bounded maximum degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21817 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A linear upper bound on the $\mathbb{Z}_p$-Ramsey number of graphs with sufficiently large $2$-packing Heath, Emily Simmons, Andrew Combinatorics Given a positive integer $k$ and graph $G$, the $\mathbb{Z}_k$-Ramsey number $R(G,\mathbb{Z}_k)$ is the least $N$ (if it exists) such that every coloring $f:E(K_N)\rightarrow \mathbb{Z}_k$ contains a copy $G'$ of $G$ such that $\sum_{e\in E(G')}f(e)=0$. Motivated by a question of Caro and Mifsud, we study the $\mathbb{Z}_k$-Ramsey number of graphs with a sufficiently large 2-packing, i.e. a set of vertices $S\subseteq V(G)$ such that $N[u]\cap N[v]=\emptyset$ for all distinct $u,v\in S$. In particular, we prove that $R(G,\mathbb{Z}_p)\leq n+6p-9$ for all $n$-vertex graphs $G$ and all primes $p$ such that $p$ divides $e(G)$, the minimum degree of $G$ is at least $1$, and there exists a $2$-packing of $G$ with size $p-1$. This upper bound improves depending on vertex degrees in the $2$-packing, with equality in certain cases. The result also implies an upper bound of the form $R(G,\mathbb{Z}_p)\leq n+C$ for $n$-vertex graphs $G$ of bounded maximum degree. |
| title | A linear upper bound on the $\mathbb{Z}_p$-Ramsey number of graphs with sufficiently large $2$-packing |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.21817 |