A Faster Algorithm to Recognize Even-Hole-Free Graphs

Hsien-Chih Chang, Hsueh-I Lu

We study the problem of determining whether an $n$-node graph $G$ has an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoo…