The eight-vertex bound for forbidden GaTEx subgraphs

Let FGT\mathfrak{F}_{\mathrm{GT}} be the set of forbidden subgraphs of GaTEx graphs, and let FFGTF\in\mathfrak{F}_{\mathrm{GT}}. The preceding discussion shows that every such forbidden subgraph has at least five vertices.

Eight-vertex bound. For all FFGTF\in\mathfrak{F}_{\mathrm{GT}}, we have

5V(F)8.5\leq |V(F)|\leq 8.

The lower bound follows from the fact that forbidden subgraphs must be primitive and cannot be pseudo-cographs, while the upper bound is motivated by the possibility of two vertex-disjoint induced P4P_4s. The claim is presented as a conjectural bound and no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Marc Hellmuth and Guillaume E. Scholz, “Resolving Prime Modules: The Structure of Pseudo-cographs and Galled-Tree Explainable Graphs”, arXiv:2211.16854 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.