Geodesic
On the connection between the chromatic number of a graph and the number of cycles, covering a vertex or an edge
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 5-13
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We prove several tight bounds on the chromatic number of a graph in terms of the minimal number of simple cycles, covering a vertex or an edge of this graph. Namely, we prove that $\chi(G)\leq k$ in the following two cases: any edge of $G$ is covered by less than $[e(k-1)!-1]$ simple cycles or any vertex of $G$ is covered by less than $[\frac{ek!}2-\frac{k+1}2]$ simple cycles. Tight bounds on the number of simple cycles covering an edge or a vertex of a $k$-critical graph are also proved. 
@article{ZNSL_2016_450_a0,
     author = {S. L. Berlov and K. I. Tyschuk},
     title = {On the connection between the chromatic number of a~graph and the number of cycles, covering a~vertex or an edge},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {5--13},
     year = {2016},
     volume = {450},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/}
}
TY  - JOUR
AU  - S. L. Berlov
AU  - K. I. Tyschuk
TI  - On the connection between the chromatic number of a graph and the number of cycles, covering a vertex or an edge
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2016
SP  - 5
EP  - 13
VL  - 450
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/
LA  - ru
ID  - ZNSL_2016_450_a0
ER  - 
%0 Journal Article
%A S. L. Berlov
%A K. I. Tyschuk
%T On the connection between the chromatic number of a graph and the number of cycles, covering a vertex or an edge
%J Zapiski Nauchnykh Seminarov POMI
%D 2016
%P 5-13
%V 450
%U http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/
%G ru
%F ZNSL_2016_450_a0
S. L. Berlov; K. I. Tyschuk. On the connection between the chromatic number of a graph and the number of cycles, covering a vertex or an edge. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 5-13. http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/

[1] K. Wagner, “Uber eine Eigenschaft der ebenen Komplexe”, Math. Ann., 114 (1937), 570–590 | DOI | MR | Zbl

[2] P. Mihok, I. Schiermeyer, “Cycle lengths and chromatic number of graphs”, Discrete Math., 286:1–2 (2004), 147–149 | DOI | MR | Zbl

[3] B. Randerath, I. Schiermeyer, “Colouring graphs with prescribed induced cycle lengths”, Discuss. Math. Graph Theory, 21 (2001), 267–281 | DOI | MR | Zbl

[4] H. Hadwiger, “Uber eine Klassifikation der Streckenkomplexe”, Vierteljahrsschr. Naturforsch. Ges. Zurich, 88 (1943), 133–142 | MR | Zbl

[5] N. Robertson, P. Seymour, R. Thomas, “Hadwiger's conjecture for K6-free graphs”, Combinatorica, 14 (1993), 279–361 | DOI | MR

[6] S. L. Berlov, V. L. Dol'nikov, “Some generalization of theorems on a vertex colouring”, J. Combinator. Theory Ser. A, 113:7 (2006), 1582–1585 | DOI | MR | Zbl

[7] G. A. Dirac, “A property of 4-chromatic graphs and some remarks on critical graphs”, J. London Math. Soc., 27 (1952), 85–92 | DOI | MR | Zbl