S. L. Berlov, I. I. Bogdanov, “On graphs with a large chromatic number containing no small odd cycles”, Zap. Nauchn. Sem. POMI, 2011, Volume 391,Pages <nobr>35

On graphs with a large chromatic number containing no small odd cycles

S. L. Berlov^a, I. I. Bogdanov^b

^a Physical and Mathematical Lyceum 239, St. Petersburg, Russia
^b Moscow Institute of Physics and Technology, Dolgoprudnyi, Moscow reg., Russia

Abstract: We present lower bounds for the number of vertices in a graph with a large chromatic number containing no small odd cycles.

Key words and phrases: chromatic number, odd cycles, girth.

UDC: 519.174.7+519.176

Received: 03.11.2011