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.