A polyhedral investigation of star colorings

Christopher Hojny (Corresponding author), Marc E. Pfetsch

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


Given a weighted undirected graph and a nonnegative integer, the maximum k-star colorable subgraph problem consists of finding an induced subgraph of which has maximum weight and can be star colored with at most 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. Finally, we derive complete balanced bipartite subgraph inequalities and present some computational results.
Original languageEnglish
Pages (from-to)59-78
Number of pages20
JournalDiscrete Applied Mathematics
Publication statusPublished - 2016
Externally publishedYes


Dive into the research topics of 'A polyhedral investigation of star colorings'. Together they form a unique fingerprint.

Cite this