Triply Existentially Complete Triangle‐Free Graphs. Issue 4 (27th May 2014) - Even‐Zohar, Chaim; Linial, Nati
Abstract A triangle‐free graph G is called k‐existentially complete if for every induced k‐vertex subgraph H of G, every extension of H to a <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjf86362w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(k+1)</alternatives>‐vertex triangle‐free graph can be realized by adding another vertex of G to H. Cherlin 1112 asked whether k‐existentially complete triangle‐free graphs exist for every k. Here, we present known and new constructions of 3‐existentially complete triangle‐free graphs.