| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418717 | Discrete Applied Mathematics | 2016 | 20 Pages |
Given a weighted undirected graph GG and a nonnegative integer kk, the maximum kk-star colorable subgraph problem consists of finding an induced subgraph of GG which has maximum weight and can be star colored with at most kk 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=2k=2. Finally, we derive complete balanced bipartite subgraph inequalities and present some computational results.
