FoCM

FoCM 2014 conference


Workshop A4 - Graph Theory and Combinatorics

No date set

Stability and Ramsey numbers for cycles and wheels

Nicolás Sanhueza

Universidad de Chile, Chile   -   nicolas@sanhueza.net

We study the structure of red-blue edge-colorings of a complete graph, in such a way that certain graphs don't appear as monochromatic subgraphs. More concretely, we consider the case of an odd positive integer $n$, and forbidden monochromatic graphs given by a red $n$-cycle $C_n$ and a blue $n$-wheel $W_n = C_n + K_1$.

Our main result is that if complete graph $G$ of appropriate size has a red-blue edge-coloring of its edges in a way such that $C_n$ is not a red subgraph of $G$ nor $W_n$ is a blue subgraph of $G$; then deleting at most two vertices we obtain a partition of the vertices of $G$ in three sets such that the edges with both ends in the same element of the partition are colored red, and blue otherwise.

We can see this result as a generalization of results previously shown by Nikiforov and Schelp, in the case where the forbidden monochromatic subgraphs are odd cycles.

As a secondary result of our proof, we obtain two bounds for the Ramsey number of $r(C_{2k+1},W_{2k+1})$: one is tighter for small values of $k$, and the other is better in the asymptotic case. The exact values for $r(C_{2k+1},W_{2k+1})$ are presently an open problem. Our bounds are a rough approximation to the conjectured values and show that they are, at least, asymptotically true.

Joint work with Maya Stein (Universidad de Chile, Chile).

View abstract PDF