✦ LIBER ✦

The Odd Girth of the Generalised Kneser Graph

✍ Scribed by Tristan Denley

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 202 KB
Volume: 18
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1996.0122

No coin nor oath required. For personal study only.

✦ Synopsis

Let X ϭ ͕ 1 , 2 , . . . , n ͖ be a set of n elements and let X ( r ) be the collection of all the subsets of X containing precisely r elements . Then the generalised Kneser graph K ( n , r , s ) (when 2 r Ϫ s р n ) is the graph with vertex set X ( r ) and edges AB for A , B X ( r ) with ͉ A ʝ B ͉ р s .

Here we show that the odd girth of the generalised Kneser graph

provided that n is large enough compared with r and s .

📜 SIMILAR VOLUMES

(2 + ?)-Coloring of planar graphs with l

(2 + ?)-Coloring of planar graphs with large odd-girth

✍ Klostermeyer, William; Zhang, Cun Quan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N

The maximum valency of regular graphs wi

The maximum valency of regular graphs with given order and odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc

On the chromatic number of the general K

On the chromatic number of the general Kneser-graph

✍ P. Frankl 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

On the girth of infinite graphs

✍ Norbert Seifter 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 599 KB

Let X be an infinite k-valent graph with polynomial growth of degree d, i.e. there is an integer d and a constant c such that fx(n) 3, d> 1, 123, there exist k-valent connected graphs with polynomial growth of degree d and girth greater than 1. This means that in general the girth of graphs with pol

The Girth of a Directed Distance-Regular

The Girth of a Directed Distance-Regular Graph

✍ D.A. Leonard; K. Nomura 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 149 KB

The smallest graph of girth 6 and valenc

The smallest graph of girth 6 and valency 7

✍ M. O'Keefe; P. K. Wong 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB

## Abstract With the aid of a computer. we give a regular graph of girth 6 and valency 7, which has 90 vertices and show that this is the unique smallest graph with these properties.