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.