The eight-vertex bound for forbidden GaTEx subgraphs
The eight-vertex bound for forbidden GaTEx subgraphs
Let be the set of forbidden subgraphs of GaTEx graphs, and let . The preceding discussion shows that every such forbidden subgraph has at least five vertices.
Eight-vertex bound. For all , we have
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 s. 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.