The vertex bound conjecture for minimal forbidden induced subgraphs of subgraph complementation number

Let c2(G)c_2(G) denote the minimum cardinality of a subgraph complementation system for a graph GG, and fix a natural number kk. A minimal forbidden induced subgraph for the property c2(G)kc_2(G)\leq k is a graph FF such that c2(F)>kc_2(F)>k but every proper induced subgraph FvF-v satisfies c2(Fv)kc_2(F-v)\leq k. Vertex bound conjecture. Every minimal forbidden induced subgraph for the property c2(G)kc_2(G)\leq k has at most 2k+22k+2 vertices.

The preceding theorem establishes that the class of graphs with c2(G)kc_2(G)\leq k 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

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.