The chromatic Ramsey number of odd wheels |
| |
Authors: | Nathalie Paul Claude Tardif |
| |
Affiliation: | Royal Military College of Canada, PO Box 17000, Station “Forces”, Kingston, Ontario, Canada K7K 7B4 |
| |
Abstract: | We prove that the chromatic Ramsey number of every odd wheel W2k+ 1, k?2 is 14. That is, for every odd wheel W2k+ 1, there exists a 14‐chromatic graph F such that when the edges of F are two‐coloured, there is a monochromatic copy of W2k+ 1 in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erd?s–Lovász conjecture on the minimum possible chromatic Ramsey number of an n‐chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198‐205, 2012 |
| |
Keywords: | Ramsey theory chromatic numbers Hedetniemi's conjecture |
|
|