✦ LIBER ✦

The chromatic Ramsey number of odd wheels

✍ Scribed by Nathalie Paul; Claude Tardif

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 110 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20575

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that the chromatic Ramsey number of every odd wheel W 2k+1 , k ≥ 2 is 14. That is, for every odd wheel W 2k+1 , there exists a 14-chromatic graph F such that when the edges of F are two-coloured, there is a monochromatic copy of W 2k+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 os-Lovász conjecture on the minimum possible chromatic Ramsey number of an n-chromatic graph.

📜 SIMILAR VOLUMES

The multi-color Ramsey number of an odd

The multi-color Ramsey number of an odd cycle

✍ Yusheng Li 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

## Abstract Let __r__~__k__~(__G__) be the __k__‐color Ramsey number of a graph __G__. It is shown that $r\_{k}(C\_{5})\le \sqrt{18^{k}\,k!}$ for __k__⩾2 and that __r__~__k__~(__C__~2__m__+ 1~)⩽(__c__^__k__^__k__!)^1/__m__^ if the Ramsey graphs of __r__~__k__~(__C__~2__m__+ 1~) are not far away fr

Size ramsey numbers of stars versus 4-ch

Size ramsey numbers of stars versus 4-chromatic graphs

✍ Oleg Pikhurko 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB 👁 1 views

## Abstract We investigate the asymptotics of the size Ramsey number __î__(__K__~1,__n__~__F__), where __K__~1,__n__~ is the __n__‐star and __F__ is a fixed graph. The author 11 has recently proved that __r̂__(__K__~1,n~,__F__)=(1+__o__(1))__n__^2^ for any __F__ with chromatic number χ(__F__)=3. He

A bound on the chromatic number using th

A bound on the chromatic number using the longest odd cycle length

✍ Sreyash Kenkre; Sundar Vishwanathan 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

## Abstract Let __G__ be a non‐bipartite graph with ℓ as the length of the longest odd cycle. Erdös and Hajnal proved that χ(__G__) ≤ ℓ + 1. We show that the only graphs for which this is tight are those that contain __K__~ℓ~ + 1 and further, if __G__ does not contain __K__~ℓ~ then χ(__G__) ≤ ℓ −1.

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

K4-free graphs with no odd hole: Even pa

K4-free graphs with no odd hole: Even pairs and the circular chromatic number

✍ Yori Zwols 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K 4 -free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K 4 -free graph with no odd hole has

The ramsey number of k5 - e

✍ C. Clapham; G. Exoo; H. Harborth; I. Mengersen; J. Sheehan 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB