The forest and bipartite-complement boundary conjecture for bipartite graph classes
The forest and bipartite-complement boundary conjecture for bipartite graph classes
Let be a tree, let denote the bipartite representation of , and let denote its bipartite complement. A class is at most factorial when its speed is bounded above by a factorial function.
Forest boundary conjecture. For any tree , the class of -free bipartite graphs is at most factorial.
In the terminology of boundary classes, this is equivalent to asserting that the class of forests and the class of their bipartite complements are the only boundary classes among hereditary properties of bipartite graphs. The conjecture is proposed as the missing step toward characterizing factorial classes defined by finitely many forbidden induced bipartite subgraphs, and remains open in the source.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Vadim Lozin and Viktor Zamaraev, “The structure and the number of P_7-free bipartite graphs”, arXiv:1607.08782 (2016).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.