✦ LIBER ✦

Induced Cycles and Chromatic Number

✍ Scribed by A.D. Scott

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 87 KB
Volume: 76
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1894

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that, for any pair of integers k, l 1, there exists an integer N(k, l ) such that every graph with chromatic number at least N(k, l ) contains either K k or an induced odd cycle of length at least 5 or an induced cycle of length at least l.

📜 SIMILAR VOLUMES

The mean chromatic number of paths and c

The mean chromatic number of paths and cycles

✍ Martin Anthony; Norman Biggs 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 245 KB

The mean chromatic number of a graph is defined. This is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. In this note, we analyse the asymptotic behaviour of the mean chromatic number for the paths and even cycles,

Cycle length parities and the chromatic

Cycle length parities and the chromatic number

✍ Christian Löwenstein; Dieter Rautenbach; Ingo Schiermeyer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract In 1966 Erdös and Hajnal proved that the chromatic number of graphs whose odd cycles have lengths at most __l__ is at most __l__+1. Similarly, in 1992 Gyárfás proved that the chromatic number of graphs which have at most __k__ odd cycle lengths is at most 2__k__+2 which was originally c

The number of shortest cycles and the ch

The number of shortest cycles and the chromatic uniqueness of a graph

✍ C. P. Teo; K. M. Koh 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 403 KB 👁 2 views

## Abstract For a graph __G__, let __g__(__G__) and σ~g~(__G__) denote, respectively, the girth of __G__ and the number of cycles of length __g__(__G__) in __G__. In this paper, we first obtain an upper bound for σ~g~(__G__) and determine the structure of a 2‐connected graph __G__ when σ~g~(__G__)

Chromatic polynomials and broken cycles

✍ S.G Hoggar 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 705 KB

The chromatic numbers of graph bundles o

The chromatic numbers of graph bundles over cycles

✍ Sandi Klavẑar; Bojan Mohar 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 565 KB

Graph bundles generalize the notion of covering graphs and products of graphs. The chromatic numbers of product bundles with respect to the Cartesian, strong and tensor product whose base and fiber are cycles are determined. ## 1. Introduction If G is a graph, V(G) and E(G) denote its vertex and e

Chromatic number and skewness

✍ Paul C Kainen 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 156 KB