A Property of Partitionable Graphs

We say that a graph satisfies the "no-week-pair" property if each pair of vertices of a graph is either in a maximum clique or in a maximum stable set

Conjecture: If a partitionable graph satisfies the "no-week-pair" property then the graph is an odd hole or an odd anti-hole.

The following graph is a counter-example to this conjecture:

take a 17-gon and and add all 3- 4- and 5-chords.

(This 17-vertex graph is the only known partitionable graph without a small transversal.)

It's still interesting if there are other such graphs (i.e. partitionable graph satisfying "no-week-pair" property). If there are then it would be nice to characterize them.

Contributed by Ara Markosian

Back to the main index for Perfect Graphs.