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).