Open access

Target Ramsey numbers in graphs

G. Chartrand Ping Zhang

Jul 2026 · Journal of Combinatorial Mathematics and Combinatorial Computing · Vol 131, pp. 353-371 · 1 citation · ⚡ 1 influential

Abstract

The Ramsey number $R(G)$ of a graph $G$ without isolated vertices is the minimum positive integer $n$ such that for every red-blue coloring of the complete graph $K_n$ of order $n$, there is a subgraph isomorphic to $G$ all of whose edges are colored the same (a monochromatic $G$). A Ramsey chain in a graph $G$ with a red-blue coloring is a sequence $G_1$, $G_2$, $\ldots$, $G_{k}$ of pairwise edge-disjoint monochromatic subgraphs of $G$ such that $G_i$ has $i$ edges for $1 \le i \le k$ and $G_i$ is isomorphic to a subgraph of $G_{i+1}$ for $1 \le i \le k-1$. The subgraphs in a Ramsey chain are the links of the chain and the terminal subgraph $G_k$ is the target link of the chain. A graph $H$ without isolated vertices is called a target graph if there exists a positive integer $n$ such that every red-blue coloring of $K_n$ results in a Ramsey chain with target link $H$. The target Ramsey number $TR(H)$ of $H$ is the minimum positive integer $n$ such that every red-blue coloring of $K_n$ results in a Ramsey chain with target link $H$. The target Ramsey number $TR(s)$ of a Ramsey chain $s$ is the minimum positive integer $n$ such that $s$ is a Ramsey chain in every red-blue coloring of $K_{n}$. We investigate graphs $H$ with the property that $TR(s) =TR(H)= R(H)$ for every Ramsey chain $s$ with target link $H$. It is shown that every graph $H$ with relatively small size has this property. Other results and open questions are also presented.

DOI Semantic Scholar

Read PDF

Similar papers

Preprint Sep 2026

Multicolor Ramsey and list Ramsey numbers for star-like trees

For a graph $H$, the $k$-color Ramsey number $r(H;k)$ is the least integer $N$ such that every $k$-edge-coloring of $K_N$ contains a monochromatic copy of $H$. A $k$-list assignment has $|L(e)|=k$ for every edge. The list Ramsey number $r_\ell(H;k)$ is the least integer $N$ for which there exists...

Qing-Qing Zhao, Ya-Ping Mao, Xiang-Qian Zhou · 0 citations

Preprint Aug 2026

A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph

Let $\zeta(G)$ denote the minimum number of parts in a partition of $V(G)$ in which every part induces either a clique or an independent set. Erd\H{o}s and Gimbel asked whether, for $G_n\sim G(n,1/2)$, the difference $\chi(G_n)-\zeta(G_n)$ tends to infinity with high probability. We resolve this problem along the full...

S. Petkov · 0 citations

Open access Sep 2026

Size Conditions for Pancyclicity of $t$-Tough Graphs

The toughness of a connected noncomplete graph $G$ is$$\tau(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G),\ c(G-S)\geq2\right\},$$where $c(G)$ is the number of components of $G$; as usual, $\tau(K_n)=\infty$. In 1973, Bondy proposed the metaconjecture that almost every nontrivial condition implying Hamiltonicity sho...

Cai-Li Jia, Xiang-Ge Liu, Lu Yong et al. · Electronic Journal of Combin... · 0 citations

Preprint Sep 2026

A Bondy-type theorem for rainbow pancyclicity in graph systems

We establish a Hamiltonian-to-pancyclic analogue of Bondy's theorem for graph systems under an aggregate degree condition. Let $\G=(G_1,\ldots,G_n)$ be a graph system on a common $n$-vertex set $V$, and write $\delta(v)=\min_{i\in[n]}d_{G_i}(v)$. If $\G$ contains a rainbow Hamilton cycle and \[ \sum_{v\in V}\delta(v)\g...

Ai-Lian Chen, Li-Ping Zhang · 0 citations

Preprint Sep 2026

Real-rootedness of the $\tau$-polynomial under graph joins

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

Preprint Sep 2026

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn...

Guo-Rong Gao, Jia-Lin He · 0 citations