Cliques, holes and the vertex coloring polytope

DOI10.1016/J.IPL.2003.11.005MaRDI QIDQ1029072zbMATHOpenAlexFDO

Authors Y. Frota, Manoel Campêlo, Ricardo C. Corrêa

Publication date 9 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2003.11.005

zbMATH Keywords

integer programminggraph coloringcombinatorial problemsfacets of polyhedra

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Polyhedral studies of vertex coloring problems: the standard formulation
• Facets of the graph coloring polytope
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• A polyhedral approach for graph coloring
• Complexity of clique-coloring odd-hole-free graphs

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A polyhedral approach for graph coloring
• Progress on perfect graphs
• The fractional chromatic number of mycielski's graphs

Cited in

(36)

• The minimum chromatic violation problem: a polyhedral approach
• Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
• The maximum-impact coloring polytope
• An integer programming approach to b-coloring
• A branch-and-cut algorithm for the connected max-\(k\)-cut problem
• A survey on vertex coloring problems
• The minimum chromatic violation problem: a polyhedral study
• Facet-generating procedures for the maximum-impact coloring polytope
• A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
• A branch-and-cut algorithm for partition coloring
• Integer linear programming formulations of the filter partitioning minimization problem
• Integer programming formulations and efficient local search for relaxed correlation clustering
• A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
• An exact algorithm for the partition coloring problem
• Fractional programming formulation for the vertex coloring problem
• A one-to-one correspondence between colorings and stable sets
• On the asymmetric representatives formulation for the vertex coloring problem
• MIP formulations for induced graph optimization problems: a tutorial
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• Crossings, colorings, and cliques
• On the recursive largest first algorithm for graph colouring
• Chromatic Gallai identities operating on Lovász number
• A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic
• A column generation based algorithm for the robust graph coloring problem
• Cycle-based facets of chromatic scheduling polytopes
• A branch-and-price approach for the partition coloring problem
• A supernodal formulation of vertex colouring with applications in course timetabling
• Complexity of clique-coloring odd-hole-free graphs
• Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
• Polyhedral studies of vertex coloring problems: the standard formulation
• Packing and partitioning orbitopes
• Clique-connecting forest and stable set polytopes
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
• A branch-and-cut procedure for the Udine course timetabling problem

This page was built for publication: Cliques, holes and the vertex coloring polytope

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