Geodesic
Relationships between the clique number, chromatic number and degree for some graphs
Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 4, pp. 10-22.

Voir la notice de l'article provenant de la source Math-Net.Ru

The existence of an independent transversal for maximal cliques of a graph of a small degree is proved. Some relationships between the clique number, the chromatic number and the degree for the graphs with a $n$-clique-cutset also are deduced.
Keywords: chromatic number, graph degree
Mots-clés : clique, transversal. 
@article{MAIS_2008_15_4_a1,
     author = {S. L. Berlov},
     title = {Relationships between the clique number, chromatic number and degree for some graphs},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {10--22},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2008_15_4_a1/}
}
TY  - JOUR
AU  - S. L. Berlov
TI  - Relationships between the clique number, chromatic number and degree for some graphs
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2008
SP  - 10
EP  - 22
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2008_15_4_a1/
LA  - ru
ID  - MAIS_2008_15_4_a1
ER  - 
%0 Journal Article
%A S. L. Berlov
%T Relationships between the clique number, chromatic number and degree for some graphs
%J Modelirovanie i analiz informacionnyh sistem
%D 2008
%P 10-22
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2008_15_4_a1/
%G ru
%F MAIS_2008_15_4_a1
S. L. Berlov. Relationships between the clique number, chromatic number and degree for some graphs. Modelirovanie i analiz informacionnyh sistem, Tome 15 (2008) no. 4, pp. 10-22. http://geodesic.mathdoc.fr/item/MAIS_2008_15_4_a1/

[1] S. L. Berlov, “Helly's property for $n$-cliques and the degree of a graph”, Zapiski Nauchnyh Seminarov POMI, 340, 2006, 5–9 | MR | Zbl

[2] N. Alon, “The strong chromatic number of a graph”, Random Struct. Alg., 3 (1992), 1–7 | DOI | MR | Zbl

[3] P. E. Haxell, “On the Strong Chromatic Number”, Combinatorics, Probability and Computing, 13:6 (2004), 857–865 | DOI | MR | Zbl

[4] M. Axenovich, R. Martin, “On the Strong Chromatic Number of Graphs”, SIAM Journal on Discrete Mathematics archive, 20:3 (2006), 741–747 | DOI | MR | Zbl

[5] P. Erdös, T. Gallai, “On minimal number of vertices representing the edges of a graph”, Publ. Math. Inst. Hung. Acad. Sci., 6 (1961), 89–96 | MR

[6] R. L. Brooks, “On coloring the nodes of a network”, Proc. Cambrige Phil. Soc., 37 (1941), 194–197 | DOI | MR

[7] B. Reed, “A Strengthening of Brooks' Theorem”, Journal of Combinatorial Theory, Series B, 76:2 (1999), 136–149 | DOI | MR | Zbl

[8] A. V. Kostochka, “Degree, density and chromatic number of graphs”, Metody Diskret. Analiz., 1980, no. 35, 45–70, 104–105 | MR | Zbl

[9] T. Jensen, B. Toft, Graph coloring problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995 | MR

[10] P. A. Catlin, “Survey of extensions of Brooks' graph coloring theorem”, Annals of the New York Academy of Sciences, 328 (1979), 95 | DOI | MR | Zbl

[11] P. Catlin, “Brooks' graph-coloring theorem and the independence number”, Journal of Combinatorial Theory, Series B, 27 (1979), 42–48 | DOI | MR | Zbl

[12] A. Beutelspacher, P. Hering, “Minimal graphs for which the chromatic number equals the maximal degree”, Ars Combinatorica, 18 (1984), 201–216 | MR | Zbl

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