Multicolor Ramsey and list Ramsey numbers for star-like trees
Abstract
For a graph H, the k-color Ramsey number r(H;k) is the least integer N such that every k-edge-coloring of KN contains a monochromatic copy of H. A k-list assignment has |L(e)|=k for every edge. The list Ramsey number rℓ(H;k) is the least integer N for which there exists a k-list assignment on E(KN) such that every coloring from the lists contains a monochromatic copy of H. Let K1,n be a star, S(n,m) the double star obtained by joining the centers of K1,n and K1,m, and Snm the graph obtained from K1,n by subdividing m edges once. Alon et al.\ conjectured that rℓ(K1,n;k)=r(K1,n;k) for all k,n≥1. In this paper, we confirm their conjecture for all k≥1 and n≥3 by a unified direct proof. For even k≥4 and under explicit parameter conditions, we prove that r(S(n,m);k)=kn+m+2 for even n and r(Snm;k)=k(n−1)+m+2 for odd n. For two colors, we establish a general list Ramsey lower bound and determine the common values of Ramsey and list Ramsey numbers for double and subdivided stars in explicit parameter ranges. These results close several gaps in the known bounds.
Related
BibTeX
@misc{zhao2026multicolor,
title = {{Multicolor Ramsey and list Ramsey numbers for star-like trees}},
author = {Qinghong Zhao and Yaping Mao and Xiangqian Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06378},
eprint = {2609.06378},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06378},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Multicolor Ramsey and list Ramsey numbers for star-like trees
AU - Qinghong Zhao
AU - Yaping Mao
AU - Xiangqian Zhou
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06378
UR - https://arxiv.org/abs/2609.06378
AB - 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_ℓ(H;k) is the least integer N for which there exists a k-list assignment on E(K_N) such that every coloring from the lists contains a monochromatic copy of H. Let K_1,n be a star, S(n,m) the double star obtained by joining the centers of K_1,n and K_1,m, and S_n^m the graph obtained from K_1,n by subdividing m edges once. Alon et al.\ conjectured that r_ℓ(K_1,n;k)=r(K_1,n;k) for all k,n≥1. In this paper, we confirm their conjecture for all k≥1 and n≥3 by a unified direct proof. For even k≥4 and under explicit parameter conditions, we prove that r(S(n,m);k)=kn+m+2 for even n and r(S_n^m;k)=k(n−1)+m+2 for odd n. For two colors, we establish a general list Ramsey lower bound and determine the common values of Ramsey and list Ramsey numbers for double and subdivided stars in explicit parameter ranges. These results close several gaps in the known bounds.
ER -