Premium
Cycle length parities and the chromatic number
Author(s) -
Löwenstein Christian,
Rautenbach Dieter,
Schiermeyer Ingo
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20450
Subject(s) - combinatorics , mathematics , modulo , chromatic scale , graph , discrete mathematics , prime (order theory)
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