Download PDF - New lower bounds on the weighted chromatic number of a graphAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

New lower bounds on the weighted chromatic number of a graph

Authors 1, 2

Affiliations

  1. IAC - Istituto per le Applicazioni del Calcolo "M. Picone", CNR - Viale del Policlinico, 137 - 00161 Roma, Italy
  2. Institute of Theoretical Computer Science (ITI), Charles University, Faculty of Mathematics and Physics, Malostranské nám. 2/25, 118 00, Prague, Czech Republic

Abstract

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

ENG
combinatorial analysis, computational analysis, optimization

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2004/24/2
Export to PBN, Opens in new tab
Pages:
183-195
Main language of publication
English
Published
2004

DOI: 10.7151/dmgt.1224

Exact and natural sciences