Fractional programming formulation for the vertex coloring problem

DOI10.1016/j.ipl.2014.06.010zbMath1358.05112arXiv1402.5769OpenAlexW2035728652MaRDI QIDQ402376

Atsushi Miyauchi, Noriyoshi Sukegawa, Tomomi Matsui

Publication date: 28 August 2014

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

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

zbMATH Keywords

combinatorial problemsvertex coloringfractional programming formulationmixed integer linear programming problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Fractional programming (90C32) Linear programming (90C05) Coloring of graphs and hypergraphs (05C15)

Related Items

Constrained integer fractional programming problem with box constraints ⋮ A column generation based algorithm for the robust graph coloring problem

Cites Work

• A supernodal formulation of vertex colouring with applications in course timetabling
• Facets of the clique partitioning polytope
• An unconstrained quadratic binary programming approach to the vertex coloring problem
• Cliques, holes and the vertex coloring polytope
• Maximum-weight stable sets and safe lower bounds for graph coloring
• A cutting plane algorithm for graph coloring
• On the asymmetric representatives formulation for the vertex coloring problem
• A branch-and-cut algorithm for graph coloring
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A survey on vertex coloring problems
• A Column Generation Approach for Graph Coloring
• Unnamed Item

This page was built for publication: Fractional programming formulation for the vertex coloring problem