{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibgkszm2hr44dmpzh54vv7pvx3rw2codxf3qk65txoz67gdz4b2ve",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfsu2nokymj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.23196v1",
  "publishedAt": "2026-02-27T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Amir Abboud",
    "Ron Safier",
    "Nathan Wallheimer"
  ],
  "textContent": "**Authors:** Amir Abboud, Ron Safier, Nathan Wallheimer\n\nA 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 \\emph{dichotomy hypothesis} characterizing which patterns $H$ make the Triangle Detection problem easier in $H$-free graphs than in general graphs. In this work, we demonstrate that this hypothesis is, in fact, equivalent to analogous hypotheses in two broader settings that a priori seem significantly more challenging: \\emph{induced} $H$-free graphs and \\emph{colored} $H$-free graphs. Our main contribution is a reduction from the induced $H$-free case to the non-induced $\\H^+$-free case, where $\\H^+$ preserves the structural properties of $H$ that are relevant for the dichotomy, namely $3$-colorability and triangle count. A similar reduction is given for the colored case. A key technical ingredient is a self-reduction to Unique Triangle Detection that preserves the induced $H$-freeness property, via a new color-coding-like reduction.",
  "title": "Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs"
}