Chorded cycle facets of the clique partitioning polytope
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 662-670 |
| Seitenumfang | 9 |
| Fachzeitschrift | Discrete applied mathematics |
| Jahrgang | 378 |
| Publikationsstatus | Veröffentlicht - 15 Jan. 2026 |
| Peer-Review-Status | Ja |
Externe IDs
| ORCID | /0000-0001-5036-9162/work/228232629 |
|---|
Schlagworte
ASJC Scopus Sachgebiete
- Diskrete Mathematik und Kombinatorik - Clique partitioning, Polyhedral geometry
- Angewandte Mathematik - Clique partitioning, Polyhedral geometry
Schlagwörter
- Clique partitioning, Polyhedral geometry