A note on the Chvátal-rank of clique family inequalities

Issue		RAIRO Oper. Res. Volume 41, Number 3, July-September 2007 Journées Polyèdres et Optimisation Combinatoire


Page(s)		289 - 294
DOI		10.1051/ro:2007022
Published online		21 August 2007

RAIRO Oper. Res. 41 (2007) 289-294
DOI: 10.1051/ro:2007022

A note on the Chvátal-rank of clique family inequalities

Arnaud Pêcher¹ and Annegret K. Wagler²

¹ Université de Bordeaux (LaBRI, INRIA), 351 cours de la Libération, 33405 Talence, France; pecher@labri.fr
² Otto-von-Guericke-Universität Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany; wagler@imo.math.uni-magdeburg.de

(Received November 21, 2006. Accepted December 21, 2006. Published online 21 August 2007.)

Abstract

Clique family inequalities $a \sum_{v \in W} x_v + (a-1) \sum_{v \in W}$ , $x_v \leq a \delta$ form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments. Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs.

Mathematics Subject Classification. 05C69, 90C10

Key words: Stable set polytope, Chvátal-rank

© EDP Sciences, ROADEF, SMAI 2007

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.