Geodesic
New lower bounds on the weighted chromatic number of a graph
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 183-195

Voir la notice de l'article provenant de la source Library of Science

In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.
Keywords: combinatorial analysis, computational analysis, optimization 
@article{DMGT_2004_24_2_a2,
     author = {Caramia, Massimiliano and Fiala, Jir{\'\i}},
     title = {New lower bounds on the weighted chromatic number of a graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {183--195},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a2/}
}
TY  - JOUR
AU  - Caramia, Massimiliano
AU  - Fiala, Jirí
TI  - New lower bounds on the weighted chromatic number of a graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 183
EP  - 195
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a2/
LA  - en
ID  - DMGT_2004_24_2_a2
ER  - 
%0 Journal Article
%A Caramia, Massimiliano
%A Fiala, Jirí
%T New lower bounds on the weighted chromatic number of a graph
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 183-195
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a2/
%G en
%F DMGT_2004_24_2_a2
Caramia, Massimiliano; Fiala, Jirí. New lower bounds on the weighted chromatic number of a graph. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 2, pp. 183-195. http://geodesic.mathdoc.fr/item/DMGT_2004_24_2_a2/