Optimization Online


A Polyhedral Investigation of Star Colorings

Christopher Hojny(hojny***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. In this article, we investigate the polyhedral properties of this problem. In particular, we characterize cases in which the inequalities that appear in a natural integer programming formulation define facets. Moreover, we identify graph classes for which these base inequalities give a complete linear description. We then study path graphs in more detail and provide a complete linear description for an alternative polytope for~$k=2$. Finally, we derive complete balanced bipartite subgraph inequalities and present some computational results.

Keywords: star coloring, sparse Hessian, complete linear description, total dual integrality, branch-and-cut

Category 1: Combinatorial Optimization (Polyhedra )

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, January 2015

Download: [PDF]

Entry Submitted: 01/13/2015
Entry Accepted: 01/30/2015
Entry Last Modified: 01/13/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society