The vertex bound conjecture for minimal forbidden induced subgraphs of subgraph complementation number
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.