Ramsey numbers of paths and graphs of the same order

Chaoping Pei; Yusheng Li

paper

Ramsey numbers of paths and graphs of the same order

arXiv:1407.7092

Abstract

For graphs $F_{n}$ and $G_{n}$ of order $n$ , if $R (F_{n}, G_{n}) = (χ (G_{n}) - 1) (n - 1) + σ (G_{n})$ , then $F_{n}$ is said to be $G_{n}$ -good, where $σ (G_{n})$ is the minimum size of a color class among all proper vertex-colorings of $G_{n}$ with $χ (G_{n})$ colors. Given $Δ (G_{n}) \leq Δ$ , it is shown that $P_{n}$ is asymptotically $G_{n}$ -good if $α (G_{n}) \leq \frac{n}{4}$ .

8 pages, 3 figures