Geodesic
A lower bound for the chromatic number of graphs with a given maximal degree and girth
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 1 (2004), pp. 99-109 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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$. 
@article{SEMR_2004_1_a8,
     author = {V. A. Tashkinov},
     title = {A lower bound for the chromatic number of graphs with a given maximal degree and girth},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {99--109},
     year = {2004},
     volume = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2004_1_a8/}
}
TY  - JOUR
AU  - V. A. Tashkinov
TI  - A lower bound for the chromatic number of graphs with a given maximal degree and girth
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2004
SP  - 99
EP  - 109
VL  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2004_1_a8/
LA  - ru
ID  - SEMR_2004_1_a8
ER  - 
%0 Journal Article
%A V. A. Tashkinov
%T A lower bound for the chromatic number of graphs with a given maximal degree and girth
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2004
%P 99-109
%V 1
%U http://geodesic.mathdoc.fr/item/SEMR_2004_1_a8/
%G ru
%F SEMR_2004_1_a8
V. A. Tashkinov. A lower bound for the chromatic number of graphs with a given maximal degree and girth. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 1 (2004), pp. 99-109. http://geodesic.mathdoc.fr/item/SEMR_2004_1_a8/

[1] B. Grünbaum, “A problem in graph coloring”, Amer. Math. Monthly, 77:10 (1970), 1088–1092 | DOI | MR

[2] O.V. Borodin, A.V. Kostochka, “On an upper bound of a graph's chromatic number, depending on the graph's degree and density”, J. Combinatorial Theory Ser. B, 23 (1977), 247–250 | DOI | MR | Zbl

[3] A.V. Kostochka, “Degree, girth and chromatic number”, Combinatorics, Proc. Fifth Hungarian Colloq. (Keszthely, 1976), Vol. II, Colloq. Math. Soc. Ja'nos Bolyai, 18, North-Holland, Amsterdam–New York, 1978, 679–696 | MR

[4] J.-H. Kim, “On Brooks' theorem for sparse graphs”, Combin. Probab. Comput., 4 (1995), 97–132 | DOI | MR | Zbl

[5] A.V. Kostochka, N.P. Mazurova, “Odna otsenka v teorii raskraski grafov”, Metody diskretnogo analiza v reshenii kombinatornykh zadach, 30 (1977), 23–29 | Zbl