Geodesic
Performance ratio of the generalized greedy algorithm for $q$-coloring problem
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2007), pp. 53-58

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

In this paper a generalized greedy algorithm finding $q$-colorable subgraph is described, where $q$ is a natural number, and it is proven that the performance ratio of the described algorithm does not exceed $\dfrac{e}{e-1}$ for arbitrary $q$. Then it is shown that the performance ratio of the simple greedy algorithm also doesn't exceed $\dfrac{e}{e-1}$. Thus, it follows that the performance ratio $2$ previously found for simple greedy algorithm is not attainable. 
@article{UZERU_2007_2_a6,
     author = {R. O. Adamyan},
     title = {Performance ratio of the generalized greedy algorithm for $q$-coloring problem},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {53--58},
     publisher = {mathdoc},
     number = {2},
     year = {2007},
     language = {hy},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2007_2_a6/}
}
TY  - JOUR
AU  - R. O. Adamyan
TI  - Performance ratio of the generalized greedy algorithm for $q$-coloring problem
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2007
SP  - 53
EP  - 58
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2007_2_a6/
LA  - hy
ID  - UZERU_2007_2_a6
ER  - 
%0 Journal Article
%A R. O. Adamyan
%T Performance ratio of the generalized greedy algorithm for $q$-coloring problem
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2007
%P 53-58
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2007_2_a6/
%G hy
%F UZERU_2007_2_a6
R. O. Adamyan. Performance ratio of the generalized greedy algorithm for $q$-coloring problem. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2007), pp. 53-58. http://geodesic.mathdoc.fr/item/UZERU_2007_2_a6/