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

From papers

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.

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

No solutions have been posted yet.