✦ LIBER ✦

Odd Wheels in Graphs

✍ Scribed by Baoguang Xu; Guoping Jin; Zhenhong Liu

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 115 KB
Volume: 84
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2073

No coin nor oath required. For personal study only.

✦ Synopsis

For k \ 1 the odd wheel of 2k+1 spokes, denoted by W 2k+1 , is the graph obtained from a cycle of length 2k+1 by adding a new vertex and joining it to all vertices of the cycle. In this paper it is shown that if a graph G of order n with minimum degree greater than 7n/12 is at least 4-chromatic then G contains an odd wheel with at most 5 spokes.

📜 SIMILAR VOLUMES

Packing Odd Circuits in Eulerian Graphs

✍ James F. Geelen; Bertrand Guenin 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 179 KB

Let C be the clutter of odd circuits of a signed graph ðG; SÞ: For nonnegative integral edge-weights w; we are interested in the linear program minðw t x: xðCÞ51; for C 2 C; and x50Þ; which we denote by (P). The problem of solving the related integer program clearly contains the maximum cut problem,

The chromatic Ramsey number of odd wheel

The chromatic Ramsey number of odd wheels

✍ Nathalie Paul; Claude Tardif 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

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 s

Short odd cycles in 4-chromatic graphs

✍ Nilli, A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 3 views

It is shown that any 4-chromatic graph on n vertices contains an odd cycle of length smaller than √ 8n.

Small odd cycles in 4-chromatic graphs

✍ Tao Jiang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB

## Abstract It is shown that every 4‐chromatic graph on __n__ vertices contains an odd cycle of length less than $2\sqrt {n}\,+3$. This improves the previous bound given by Nilli [J Graph Theory 3 (1999), 145–147]. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 115–117, 2001

Graphs with given odd sets

✍ Chen, Guantao; Schelp, Richard H.; ?olt�s, ?ubom�r 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

Given a graph G, its odd set is a set of all integers k such that G has odd number of vertices of degree k. We show that if two graphs G and H of the same order have the same odd sets then they can be obtained from each other by succesive application of the following two operations: • add or remove

Even and odd holes in cap-free graphs

✍ Conforti, Michele; Cornu�jols, G�rard; Kapoor, Ajai; Vu?kovi?, Kristina 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB 👁 1 views

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a g