The Maximum k-Colorable Subgraph Problem and Related Problems

DOI10.1287/IJOC.2021.1086MaRDI QIDQ5084675zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

semidefinite programmingJohnson graphsHamming graphsstable setchromatic number of a graph\(k\)-colorable subgraph problemgeneralized theta number

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

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

Cites work

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

Cited in

(15)

• Partitioning through projections: strong SDP bounds for large graph partition problems
• On Integrality in Semidefinite Programming for Discrete Optimization
• 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
• The maximum $k$-colorable subgraph problem and related problems
• Fair allocation of indivisible items with conflict graphs
• Parameterized complexity of maximum edge colorable subgraph
• scientific article; zbMATH DE number 1433954 (Why is no real title available?)

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)