A polyhedral investigation of star colorings

Christopher Hojny, Marc E. PfetschDiscret. Appl. Math 2016 · DOI · OpenReview

Abstract

Given a weighted undirected graph G<math><mi is="true">G</mi></math> and a nonnegative integer k<math><mi is="true">k</mi></math>, the maximum k<math><mi is="true">k</mi></math>-star colorable subgraph problem consists of finding an induced subgraph of G<math><mi is="true">G</mi></math> which has maximum weight and can be star colored with at most k<math><mi is="true">k</mi></math> 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<math><mi is="true">k</mi><mo is="true">=</mo><mn is="true">2</mn></math>. Finally, we derive complete balanced bipartite subgraph inequalities and present some computational results.
BibTeX
@article{hojny2016polyhedral,
  author = {Christopher Hojny and Marc E. Pfetsch},
  title = {{A polyhedral investigation of star colorings}},
  journal = {Discret. Appl. Math.},
  year = {2016},
  doi = {10.1016/j.dam.2016.03.003},
}

Loading related content...

Figure