The Maximum k-Colorable Subgraph Problem and Related Problems

DOI10.1287/IJOC.2021.1086OpenAlexW3162383213MaRDI QIDQ5084675FDOQ5084675

Authors: Olga Kuryatnikova, Renata Sotirov, Juan Vera

Publication date: 28 June 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.09644

Recommendations

Semi-definite positive programming relaxations for graph $K_n$-coloring in frequency assignment.
Branch-cut-and-propagate for the maximum $k$-colorable subgraph problem with symmetry
Semidefinite programming relaxations for graph coloring and maximal clique problems
The maximum $k$-colorable subgraph problem and orbitopes
On semidefinite programming relaxations of maximum $k$-section

semidefinite programming Johnson graphs Hamming graphs stable set chromatic number of a graph $k$-colorable subgraph problem generalized theta number

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

Reducibility among combinatorial problems
Optimization, approximation, and complexity classes
Geometric algorithms and combinatorial optimization
Title not available (Why is that?)
INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
On the Shannon capacity of a graph
The node-deletion problem for hereditary properties is NP-complete
Symmetry groups, semidefinite programs, and sums of squares
On the copositive representation of binary and continuous nonconvex quadratic programs
Title not available (Why is that?)
Title not available (Why is that?)
Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
The Boolean quadratic polytope: Some characteristics, facets and relatives
Laplacian eigenvalues and the maximum cut problem
Branch-cut-and-propagate for the maximum $k$-colorable subgraph problem with symmetry
Graphs with Given Group and Given Graph-Theoretical Properties
Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION
The Operator $\Psi$ for the Chromatic Number of a Graph
The maximum $k$-colorable subgraph problem and orbitopes
New bounds for the $\max$-$k$-cut and chromatic number of a graph
The maximum k-colorable subgraph problem for chordal graphs
A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
SDP relaxations for some combinatorial optimization problems
.878-approximation algorithms for MAX CUT and MAX 2SAT
A comparison of the Delsarte and Lovász bounds
Title not available (Why is that?)
Title not available (Why is that?)
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
On equivalence of semidefinite relaxations for quadratic matrix programming
Solving VLSI design and DNA sequencing problems using bipartization of graphs
A new table of constant weight codes
The approximation of maximum subgraph problems
Semidefinite programming relaxations for the graph partitioning problem
Polyhedral results for the bipartite induced subgraph problem
Experimental and Efficient Algorithms
Independence number of products of Kneser graphs
On approximate graph colouring and MAX-$k$-CUT algorithms based on the $\vartheta$-function
Title not available (Why is that?)
The MIN-cut and vertex separator problem
Semidefinite relaxations for partitioning, assignment and ordering problems
Finding a maximum-weight induced $k$-partite subgraph of an $i$-triangulated graph
Constructive algorithms for the partial directed weighted improper coloring problem
Semidefinite programming and eigenvalue bounds for the graph partition problem
An efficient semidefinite programming relaxation for the graph partition problem
On spectrum sharing games
Title not available (Why is that?)
On the chromatic number, colorings, and codes of the Johnson graph
Online algorithms for the maximum $k$-colorable subgraph problem
A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: a review

Cited In (14)

Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem
Mathematical programming models and exact algorithms
Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
Maximum subgraph problem for 3-regular Knödel graphs and its wirelength
On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
Maximum number of colors: C-coloring and related problems
Improved Inapproximability Results for Maximum k-Colorable Subgraph
Upper and lower bounds based on linear programming for the b-coloring problem
Maximal ambiguously $k$-colorable graphs
Fair allocation of indivisible items with conflict graphs
Parameterized complexity of maximum edge colorable subgraph
Title not available (Why is that?)
Partitioning through projections: strong SDP bounds for large graph partition problems
On Integrality in Semidefinite Programming for Discrete Optimization

This page was built for publication: The Maximum k-Colorable Subgraph Problem and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084675)