Some remarks on the uncolored versions of the original CFI-graphs

Yijia Chen, Jörg Flum, Mingjun Liu

The CFI-graphs, named after Cai, Fürer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are colored graphs, an…