RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2004 Volume 1, Pages 99–109 (Mi semr9)

This article is cited in 3 papers

Research papers

A lower bound for the chromatic number of graphs with a given maximal degree and girth

V. A. Tashkinov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: For every $g\ge 3$ we prove the existence of a simple graph with maximum degree at most $6$, girth at least $g$ and chromatic number at least $4$.

UDC: 519.17

MSC: 05C

Received December 1, 2004, published December 9, 2004



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024