Chromatic Gallai identities operating on Lovász number
From MaRDI portal
Publication:2452384
DOI10.1007/s10107-013-0636-1zbMath1291.05057OpenAlexW2162372009MaRDI QIDQ2452384
Philippe Meurdesoif, Denis Cornaz
Publication date: 2 June 2014
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-013-0636-1
Semidefinite programming (90C22) Linear programming (90C05) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Solving vertex coloring problems as maximum weight stable set problems ⋮ A note on selective line-graphs and partition colorings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Facet-inducing web and antiweb inequalities for the graph coloring polytope
- The chromatic gap and its extremes
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Cliques, holes and the vertex coloring polytope
- The ellipsoid method and its consequences in combinatorial optimization
- The sandwich theorem
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- Tibor Gallai
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On NP-hardness of the clique partition -- independence number gap recognition and related problems
- On the asymmetric representatives formulation for the vertex coloring problem
- A one-to-one correspondence between colorings and stable sets
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- Approximate graph coloring by semidefinite programming
- A comparison of the Delsarte and Lovász bounds
- The NP-Completeness of Edge-Coloring
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- The fractional chromatic number of mycielski's graphs
- On the recursive largest first algorithm for graph colouring
- Sur le coloriage des graphs
This page was built for publication: Chromatic Gallai identities operating on Lovász number
