New lower bounds on the weighted chromatic number of a graph
Massimiliano Caramia ; Jirí Fiala
Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 183-195 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270419 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1224,
     author = {Massimiliano Caramia and Jir\'\i\ Fiala},
     title = {New lower bounds on the weighted chromatic number of a graph},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {183-195},
     zbl = {1063.05042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1224}
}

Massimiliano Caramia; Jirí Fiala. New lower bounds on the weighted chromatic number of a graph. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 183-195. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1224/

[000] [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. | Zbl 0394.05022

[001] [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.

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

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

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

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

[006] [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.

[007] [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. | Zbl 0884.90144

[008] [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. | Zbl 0768.68177

[009] [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. | Zbl 0866.05025