Talk:Triangle-free graph

re: triangle-finding problem

I changed the bound for the $A^{3}$ algorithm to $O(n^{3})$ instead of $O(n^{2.376})$. 2.376 is the best-known exponent right now, yes, (see here), but it hasn't been implemented anywhere (this is mentioned on the link), and using $n^{2.376}$ instead of the classical and recognizable $n^{3}$ is confusing or misleading to anyone who doesn't follow recent developments in numerical linear algebra. Charibdis (talk) 01:12, 22 December 2010 (UTC)

I undid your changes since the article makes no sense after them. In particular, the n³ matrix multiplication algorithm is slower than the m^1.41 time bound of the other algorithm, even for dense matrices, so it is nonsensical to say that the matrix algorithm (without the fast matrix multiplication techniques) is an improvement on the other algorithm. —David Eppstein (talk) 02:48, 22 December 2010 (UTC)

Independent set of size √n

We need a reference for "An independent set of √n vertices in an n-vertex triangle-free graph is easy to find." This would imply that the 5-cycle is 3-colorable. Should it perhaps be the floor of √n ? — Preceding unsigned comment added by Gruberan (talk • contribs) 21:29, 24 November 2012 (UTC)

I think that except for K₂ and C₅ it's the ceiling, not the floor. The reasoning is that, if its maximum degree is Δ, then either $\Delta \geq {\sqrt {n}}$ in which case we find a large independent set as the neighborhood of one vertex, or $\Delta \leq {\sqrt {n}}$ in which case by Brooks' theorem there exists a Δ-coloring and one of the color classes is large enough. The exceptional cases for Brooks' theorem are the odd cycles and complete graphs, but the only ones of those that cause any problem are K₂ and C₅. I agree that a source for this reasoning would be appropriate. —David Eppstein (talk) 22:00, 24 November 2012 (UTC)