Chorded cycle facets of the clique partitioning polytope

Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung

Abstract

The q-chorded k-cycle inequalities are a class of valid inequalities for the clique partitioning polytope. It is known that for [Formula Presented], these inequalities induce facets of the clique partitioning polytope if and only if k is odd. Here, we characterize such facets for arbitrary k and q. More specifically, we prove that the q-chorded k-cycle inequalities induce facets of the clique partitioning polytope if and only if two conditions are satisfied: k=1 mod q, and if k=3q+1 then q=3 or q is even. This establishes the existence of many facets induced by q-chorded k-cycle inequalities beyond those previously known.

Details

OriginalspracheEnglisch
Seiten (von - bis)662-670
Seitenumfang9
FachzeitschriftDiscrete applied mathematics
Jahrgang378
PublikationsstatusVeröffentlicht - 15 Jan. 2026
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0001-5036-9162/work/228232629

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • Clique partitioning, Polyhedral geometry