The Operator $\Psi$ for the Chromatic Number of a Graph
From MaRDI portal
Publication:3629507
DOI10.1137/050648237zbMath1213.05080OpenAlexW2097900174MaRDI QIDQ3629507
Nebojša Gvozdenović, Monique Laurent
Publication date: 27 May 2009
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/050648237
Semidefinite programming (90C22) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)
Related Items
Dynamic coloring of graphs having no \(K_5\) minor, Spotting Trees with Few Leaves, Algebras, graphs and thetas, Matrix Relaxations in Combinatorial Optimization, Spotting Trees with Few Leaves, Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone, Copositive programming motivated bounds on the stability and the chromatic numbers, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, The Maximum k-Colorable Subgraph Problem and Related Problems, Colorings of complements of line graphs, Copositivity and constrained fractional quadratic problems, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Copositive optimization -- recent developments and applications, Collective dynamics of phase-repulsive oscillators solves graph coloring problem, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, On the computational complexity of membership problems for the completely positive cone and its dual, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, An axiomatic duality framework for the theta body and related convex corners, A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs, Block-diagonal semidefinite programming hierarchies for 0/1 programming, Convex Relaxations and Integrality Gaps, Copositive Programming, Invariant Semidefinite Programs, Semidefinite and linear programming integrality gaps for scheduling identical machines, Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming, Completely positive reformulations for polynomial optimization, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme
