Geodesic
The gulf between the clique number and its upper estimate provided by fractional coloring of the nodes
Serdica Mathematical Journal, Tome 43 (2017) no. 2, pp. 111-126 Cet article a éte moissonné depuis la source Bulgarian Digital Mathematics Library

Voir la notice de l'article

It is well known that coloring the nodes can be used to establish upper bounds for the clique number of a graph which in turn can be used to speed up practical clique search algorithms. E. Balas and J. Xue suggested factional coloring while S. Szabó and B. Zaválnij suggested triangle free coloring of the nodes to get tighter bounds. The main result of this paper is that the gap between the clique number and the upper bound provided by the coloring scheme combining the fractional and triangle free colorings still can be arbitrarily large.
Keywords: clique, maximum clique, independent set, vertex coloring, 3-clique free coloring, clique search algorithm, 05C15 
@article{SMJ2_2017_43_2_a1,
     author = {Szab\'o, S. and Zav\'alnij, B.},
     title = {The gulf between the clique number and its upper estimate provided by fractional coloring of the nodes},
     journal = {Serdica Mathematical Journal},
     pages = {111--126},
     year = {2017},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SMJ2_2017_43_2_a1/}
}
TY  - JOUR
AU  - Szabó, S.
AU  - Zaválnij, B.
TI  - The gulf between the clique number and its upper estimate provided by fractional coloring of the nodes
JO  - Serdica Mathematical Journal
PY  - 2017
SP  - 111
EP  - 126
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SMJ2_2017_43_2_a1/
LA  - en
ID  - SMJ2_2017_43_2_a1
ER  - 
%0 Journal Article
%A Szabó, S.
%A Zaválnij, B.
%T The gulf between the clique number and its upper estimate provided by fractional coloring of the nodes
%J Serdica Mathematical Journal
%D 2017
%P 111-126
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/SMJ2_2017_43_2_a1/
%G en
%F SMJ2_2017_43_2_a1
Szabó, S.; Zaválnij, B. The gulf between the clique number and its upper estimate provided by fractional coloring of the nodes. Serdica Mathematical Journal, Tome 43 (2017) no. 2, pp. 111-126. http://geodesic.mathdoc.fr/item/SMJ2_2017_43_2_a1/