zbMATH — the first resource for mathematics

Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring. (English) Zbl 1059.05052
Summary: The Lovász \(\theta\)-number is a way to approximate the independence number of a graph, but also its chromatic number. We express the Lovász bound as the continuous relaxation of a discrete Lovász \(\theta\)-number which we derive from D. Karger et al.’s formulation [J. ACM 45, 246–265 (1998; Zbl 0904.68116)], and which is equal to the chromatic number. We also give another relaxation à la Schrijver-McEliece, which is better than the Lovász \(\theta\)-number.

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
90C27 Combinatorial optimization
Full Text: DOI
[1] Alizadeh, F., Haeberly, J.-P., Nayakkankuppam, M.V., Overton, M.L. (1997): SDPPack User?s Guide, version 0.8 beta. Technical report, NYU Computer Science Dpt, March 1997. URL: http://www.cs.nyu.edu/phd_students/madhu/sdppack/sdppack.html
[2] Alon, N. (1994): Explicit Ramsey graphs and orthonormal labelings. Electron. J. Comb. 1, # R12 · Zbl 0814.05056
[3] Alon, N., Kahale, N. (1998): Approximating the independence number via the ?-function. Math. Program. 80, 253-264 · Zbl 0895.90169
[4] Feige, U., Kilian, J. (1996): Zero Knowledge and the Chromatic Number. In: Proceedings of the 11th Annual IEEE Conference in Computing Complexity (preliminary version), pp. 278-287 · Zbl 0921.68089
[5] Frieze, A., Jerrum, M. (1995): Improved approximation algorithms for MAX k-cut and MAX BISECTION. In: Proceedings of the Fourth MPS Conference on Integer Programming and Combinatorial Optimization. Springer · Zbl 1135.90420
[6] Goemans, M.X., Williamson, D.P. (1995): Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42, 1115-1145 · Zbl 0885.68088 · doi:10.1145/227683.227684
[7] Horn, R.A., Johnson, C.R. (1985): Matrix Analysis. Cambridge University Press, Cambridge (reedited 1999) · Zbl 0576.15001
[8] Jensen, T.R., Toft, B. (1995): Graph coloring problems. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York
[9] Karger, D., Motwani, R., Sudan, M. (1998): Approximate graph coloring by semidefinite programming. J. ACM 45 (2), 246-265, March 1998 · Zbl 0904.68116 · doi:10.1145/274787.274791
[10] Knuth, D. (1994): The Sandwich Theorem. Electron. J. Comb. 1, # A1, 48 pp. · Zbl 0810.05065
[11] Lemaréchal, C., Oustry, F. (1999): Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization. Rapport de Recherche Nr. 3710. Inria · Zbl 1160.90639
[12] Lovász, L. (1979): On the Shannon Capacity of a Graph. IEEE Trans. Inf. Theory IT-25 (1), 1-7 · Zbl 0395.94021
[13] Lund, C., Yannakakis, M. (1994): On the hardness of approximating minimization problems. J. ACM 41 (5), 960-981 · Zbl 0814.68064 · doi:10.1145/185675.306789
[14] McEliece, R.J., Rodemich, E.R., Rumsey Jr., H.C. (1978): The Lovász Bound and Some Generalizations. J. Comb. Inf. Syst. Sci. 3 (3), 134-152 · Zbl 0408.05031
[15] Poljak, S., Rendl, F., Wolkowicz, H. (1995): A recipe for semidefinite relaxation for (0-1)-quadratic programming. J. Glob. Optim. 7, 51-73 · Zbl 0843.90088 · doi:10.1007/BF01100205
[16] Schrijver, A. (1979): A Comparison of the Delsarte and Lovász Bounds. IEEE Trans. Inf. Theory IT-25 (4), 425-429 · Zbl 0444.94009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.