The vertex bound conjecture for minimal forbidden induced subgraphs of subgraph complementation number
The vertex bound conjecture for minimal forbidden induced subgraphs of subgraph complementation number
Let denote the minimum cardinality of a subgraph complementation system for a graph , and fix a natural number . A minimal forbidden induced subgraph for the property is a graph such that but every proper induced subgraph satisfies . Vertex bound conjecture. Every minimal forbidden induced subgraph for the property has at most vertices.
The preceding theorem establishes that the class of graphs with is characterized by finitely many forbidden induced subgraphs, but does not give an explicit bound on their orders. This conjecture proposes a linear bound based on results concerning linear forests.
Sources & referencesView supporting material
Primary source
Calum Buchanan, Christopher Purcell and Puck Rombach, “Subgraph complementation and minimum rank”, arXiv:2101.06180 (2022).
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.