Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs

Amir Abboud, Ron Safier, Nathan Wallheimer

A recent paper by the authors (ITCS'26) initiates the study of the Triangle Detection problem in graphs avoiding a fixed pattern H as a subgraph and proposes a dichotomy hypothesis…