Even-hole-free circulants,

Given interer $k \geq 1$ and $m \geq 0$, let us introduce a graph $G(k,m) = (V,E)$ with circular symmetry as follows: $V = {\bf Z}_n = \{1,...,n\}$, where $n = k(2m+1)$, and $(i,j) \in E$ iff

$$i-j + t \, (2m+1) = 0 \; or \; +1 \; or \; -1 \;\; (mod \; n)$$

for some integer $t$. (For convenience, the loops $i=j$ are included.) E.g. if $k=5, m=2$ then $n = 25$ and $(i,j) \in E$ iff $i - j (mod \; 25) \in \{4,5,6; 9,10,11; 14,15,16; 19,20,21; 24,0,1\}.$

It is not difficult to check that $G(k,m)$ has no even holes, (in fact, it can only have holes of length $2m+1$); furthermore,

$\omega(G(k,m)) = 2k, \;$ $2k + \lceil k/m \rceil \leq \chi(G(k,m)) \leq 2k + \lceil k/m \rceil + 1$,

and $G(k,m)$ satisfies Conjectures 2,3,4 from the section "Even-Hole-Free Graphs".

Conjecture. Every non-empty even-hole-free circulant is isomorphic to a $G(k,m)$.

Contributed by Diogo Andrade, Endre Boros, and Vladimir Gurvich

Back to the main index for Perfect Graphs.