Testing $C_k$-freeness in bounded-arboricity graphs

Talya Eden, Reut Levi, Dana Ron

We study the problem of testing $C_k$-freeness ($k$-cycle-freeness) for fixed constant $k>3$ in graphs with bounded arboricity (but unbounded degrees). In particular, we are inte…