The forest and bipartite-complement boundary conjecture for bipartite graph classes

About 10 years old · traced to

Let TT be a tree, let TbT^b denote the bipartite representation of TT, and let Tb‾\overline{T^b} 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 TT, the class of {T,Tb‾}\{T,\overline{T^b}\}-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.

References

Primary source

Vadim Lozin and Viktor Zamaraev, “The structure and the number of P_7-free bipartite graphs”, arXiv:1607.08782 (2016).

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.