Multicolor Ramsey Number for Double Stars

DOI10.1016/J.DISC.2024.114034MaRDI QIDQ6416401zbMATH OpenOpenAlexFDO

Publication date 7 November 2022

Full work available at URL https://doi.org/10.1016/j.disc.2024.114034

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: For a graph

H

and integer

k g e 1

, let

r (H; k)

and

r_{e} l l (H; k)

denote the

k

-color Ramsey number and list Ramsey number of

H

, respectively. Motivated by the work of Alon, Buci'c, Kalvari, Kuperwasser and Szab'o, who initiated the systematic study of list Ramsey numbers of graphs and hypergraphs, and conjectured that

r (K_{1, n}; k)

and

r_{e} l l (K_{1, n}; k)

are always equal, we study the

k

-color Ramsey number for double stars

S (n, m)

, where

n g e m g e 1

. To the best of our knowledge, little is known on the exact value of

r (S (n, m); k)

when

k g e 3

. A classic result of ErdH{o}s and Graham from 1975 asserts that

r (T; k) > k (n - 1) + 1

for every tree

T

with

n g e 1

edges and

k

sufficiently large such that

n

divides

k - 1

. Using a folklore double counting argument in set system and the edge chromatic number of complete graphs, we prove that if

k

is odd and

n

is sufficiently large compared with

m

and

k

, then [ r(S(n,m);k)=kn+m+2.] This is a step in our effort to determine whether

r (S (n, m); k)

and

r_{e} l l (S (n, m); k)

are always equal, which remains wide open. We also prove that

r (S_{n}^{m}; k) = k (n - 1) + m + 2

if

k

is odd and

n

is sufficiently large compared with

m

and

k

, where

1 l e m l e n

and

S_{n}^{m}

is obtained from

K_{1, n}

by subdividing

m

edges each exactly once. We end the paper with some observations towards the list Ramsey number for

S (n, m)

and

S_{n}^{m}

.

Recommendations

Cited in

(1)

On the Ramsey number of the double star

This page was built for publication: Multicolor Ramsey Number for Double Stars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416401)