Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time? The $k$-cycle problem is as follows:

Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.

Question: Does there exist a (proper) $k$-cycle in $G$?

Background: For any fixed $k$, we can solve $2k$-cycle in $O(n^2)$ time.


  Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J.  Discrete Math. 10(2): 209-222 (1997)


However, it is not known if we can solve 3-cycle (i.e. 3-clique) in less than matrix multiplication time.

My Question: Assuming that $G$ contains no 4-cycles, can we solve the 3-cycle problem in $O(n^2)$ time?

David suggested an approach for solving this variant of the 3-cycle problem in $O(n^{2.111})$ time.
Yes, this is known. It appears in one of the must-cite references on triangle finding...

Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf) It is a simple procedure based on properties of breadth-first search.

So, if your graph is 4-cycle free and there is a triangle, their algorithm must output it, because it cannot output a 5-cycle or larger.