Target Ramsey numbers in graphs
Journal of Combinatorial Mathematics and Combinatorial Computing · 22.07.2026 · 131 · 353-371
DOI: 10.61091/jcmcc131-17 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Mathematics and Combinatorial Computing, online erschienen am 22.07.2026. Verfasst von Gary Chartrand und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Chartrand, G., & Zhang, P. (2026). Target Ramsey numbers in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 131, 353-371. https://doi.org/10.61091/jcmcc131-17
Vancouver
Chartrand G, Zhang P. Target Ramsey numbers in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. 2026;131:353-371. doi:10.61091/jcmcc131-17
BibTeX
@article{Chartrand2026,
author = {Chartrand, Gary and Zhang, Ping},
title = {Target Ramsey numbers in graphs},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2026},
volume = {131},
pages = {353--371},
doi = {10.61091/jcmcc131-17}
}
EUVIMED