✦ LIBER ✦

Cycle length parities and the chromatic number

✍ Scribed by Christian Löwenstein; Dieter Rautenbach; Ingo Schiermeyer

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 164 KB
Volume: 64
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20450

No coin nor oath required. For personal study only.

✦ Synopsis

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 conjectured by Bollobás and Erdös. Here we consider the influence of the parities of the cycle lengths modulo some odd prime on the chromatic number of graphs. As our main result we prove the following: Let p be an odd prime, k∈ℕ and I⊆{0, 1, …, p−1} with |I|≤p−1. If G is a graph such that the set of cycle lengths of G contains at most k elements which are not in I modulo p, then χ(G)≤(1+|I|/(p−|I|))k+p(p−1)(r(2__p__, 2__p__)+1)+1 where r(p, q) denotes the ordinary Ramsey number. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 210–218, 2010

📜 SIMILAR VOLUMES

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.

Induced Cycles and Chromatic Number

✍ A.D. Scott 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 87 KB

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.

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,

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

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__)

Zero Knowledge and the Chromatic Number

✍ Uriel Feige; Joe Kilian 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 483 KB

We present a new technique, inspired by zero-knowledge proof systems, for proving lower bounds on approximating the chromatic number of a graph. To illustrate this technique we present simple reductions from max-3-coloring and max-3-sat, showing that it is hard to approximate the chromatic number wi