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 
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/
@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},
     year = {2007},
     number = {2},
     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
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
%U http://geodesic.mathdoc.fr/item/UZERU_2007_2_a6/
%G hy
%F UZERU_2007_2_a6

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.

[1] G. Narasimhan, Computer Sciences Technical Report S64, 1989, 49–57

[2] M. Garey, D. Johnson, Computers and Intractability, San Francisco, 1979, 194 pp. | MR

[3] M. Yannakakis, F. Gavril, “The maximum $k$-colorable subgraph problem for chordal graphs”, Information Processing Latters, 24:2 (1987), 133–137 | DOI | MR | Zbl

[4] S.E. Markosyan, “O nekotorykh algoritmakh i svoistvakh grafov sravneniya”, Izv. NAH Armenii, Matematika, 35:2 (2000), 67–78 | MR | Zbl

[5] A. Schrijver, “Unions of Ditected Paths and Chains”, Combinatorial Optimization, 1st edition, Springer-Verlag, Berlin–Heidelberg–New York, 2003, 224–226 | MR

[6] M. Grötshcel, L. Lovász, r A. Schrijve, “The Ellipsoid Method and its Consequences in Combinatorial Optimization”, Combinatorica, 1:2 (1981), 169–197 | DOI | MR

[7] F. Gavril, “Algorithms on circular-arc graphs”, Networks, 4 (1974), 357–369 | DOI | MR | Zbl