Given interer and , let us introduce a graph with circular symmetry as follows: , where , and iff
for some integer . (For convenience, the loops are included.) E.g. if then and iff
It is not difficult to check that has no even holes, (in fact, it can only have holes of length ); furthermore,
and satisfies Conjectures 2,3,4 from the section "Even-Hole-Free Graphs".
Conjecture. Every non-empty even-hole-free circulant is isomorphic to a .
Contributed by Diogo Andrade, Endre Boros, and Vladimir Gurvich
Back to the main index for Perfect Graphs.