A polyhedral investigation of star colorings
Lists
Only you see this
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...