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/

[1] D. Brelaz, New methods to color the vertices of a graph, Communications of the ACM 22 (1979) 251-256, doi: 10.1145/359094.359101.

[2] M. Caramia and P. Dell'Olmo, Iterative coloring extension of a maximum clique, Naval Research Logistics 48 (2001) 518-550, doi: 10.1002/nav.1033.

[3] M. Caramia and P. Dell'Olmo, Solving the minimum weighted coloring problem, Networks 38 (2001) 88-101, doi: 10.1002/net.1028.

[4] B. Descartes, Solution to advanced problem, No 4526. Amer. Math. Monthly 61 (1954) 532.

[5] M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman and Co.: San Francisco, 1979).

[6] M. Kubale, Introduction to Computational Complexity and Algorithmic Graph Coloring (Wydawnictwo GTN, Gdańsk, 1998).

[7] M. Kubale and B. Jackowski, A generalized implicit enumeration algorithm for graph coloring, Communications of the ACM 28 (1985) 412-418, doi: 10.1145/3341.3350.

[8] A. Mehrotra and M.A. Trick, A column generation approach for graph coloring, INFORMS J. on Computing 8 (1996) 344-354, doi: 10.1287/ijoc.8.4.344.

[9] T.J. Sager and S. Lin, A Pruning procedure for exact graph coloring, ORSA J. on Computing 3 (1993) 226-230, doi: 10.1287/ijoc.3.3.226.

[10] E.C. Sewell, An Improved Algorithm for Exact Graph Coloring, in: D.S. Johnson and M.A. Trick, eds., DIMACS Series in Computer Mathematics and Theoretical Computer Science 26 (1996) 359-373.