A polyhedral investigation of star colorings

作者：Hojny Christopher^*; Pfetsch Marc E

来源：Discrete Applied Mathematics, 2016, 208: 59-78.

DOI：10.1016/j.dam.2016.03.003

• Star coloring
• Sparse Hessian
• Complete linear description
• Total dual integrality
• Branch-and-cut

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.

• 出版日期2016-7-31