English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Despite the fact that some vertex coloring problems are polynomially solvableon certain graph classes, most of these problems are not "under control" from apolyhedral point of view. The equivalence between \emph{optimization} and\emph{polyhedral separation} suggests that, for these problems, there mustexist formulations admitting some elegant characterization for the polytopesassociated to them. Therefore, it is interesting to study known formulationsfor vertex coloring with the goal of finding such characterizations. In thiswork we study the asymmetric representatives formulation and we show that thecorresponding coloring polytope, for a given graph $G$, can be interpreted asthe stable set polytope of another graph obtained from $G$. This result allowsus to derive complete characterizations for the corresponding coloring polytopefor some families of graphs, based on known complete characterizations for thestable set polytope.

Polyhedral studies of vertex coloring problems: The asymmetric representatives formulation