  In a seminal work, Chiba and Nishizeki [SIAM J. Comput. `85] developed
subgraph listing algorithms for triangles, 4-cycle and $k$-cliques, where $k
\geq 3.$ The runtimes of their algorithms are parameterized by the number of
edges $m$ and the arboricity $\alpha$ of a graph. The arboricity $\alpha$ of a
graph is the minimum number of spanning forests required to cover it. Their
work introduces: * A triangle listing algorithm that runs in $O(m\alpha)$ time.
* An output-sensitive 4-Cycle-Listing algorithm that lists all 4-cycles in
$O(m\alpha + t)$ time, where $t$ is the number of 4-cycles in the graph. * A
k-Clique-Listing algorithm that runs in $O(m\alpha^{k-2})$ time, for $k \geq
4.$
  Despite the widespread use of these algorithms in practice, no improvements
have been made over them in the past few decades. Therefore, recent work has
gone into studying lower bounds for subgraph listing problems. The works of
Kopelowitz, Pettie and Porat [SODA `16] and Vassilevska W. and Xu [FOCS `20]
showed that the triangle-listing algorithm of Chiba and Nishizeki is optimal
under the $\mathsf{3SUM}$ and $\mathsf{APSP}$ hypotheses respectively. However,
it remained open whether the remaining algorithms were optimal.
  In this note, we show that in fact all the above algorithms are optimal under
popular hardness conjectures. First, we show that the
$\mathsf{4}\text{-}\mathsf{Cycle}\text{-}\mathsf{Listing}$ algorithm is tight
under the $\mathsf{3SUM}$ hypothesis following the techniques of Jin and Xu
[STOC `23], and Abboud, Bringmann and Fishcher [STOC `23] . Additionally, we
show that the $k\text{-}\mathsf{Clique}\text{-}\mathsf{Listing}$ algorithm is
essentially tight under the exact $k$-clique hypothesis by following the
techniques of Dalirooyfard, Mathialagan, Vassilevska W. and Xu [STOC `24].
These hardness results hold even when the number of 4-cycles or $k$-cliques in
the graph is small.
