The crown-subgraph conjecture for representation numbers of bipartite graphs

Let GG be a bipartite graph. For κ05 \kappa_0\geq 5, let Hκ0,κ0H_{\kappa_0,\kappa_0} be a largest induced crown graph in GG, and let R(G) \mathcal{R}(G) denote the representation number of GG.

Crown-subgraph conjecture. The representation number of GG equals either

κ02\left\lceil\frac{\kappa_0}{2}\right\rceil

or

1+κ02.\left\lceil\frac{1+\kappa_0}{2}\right\rceil.

This conjecture proposes that the representation number is determined, up to the two displayed possibilities, by the largest induced crown graph in GG. The source presents it in the conclusion and gives no evidence of a resolution.

Sources & referencesView supporting material

Primary source

Khyodeno Mozhui and K. V. Krishna, “On the Permutation-Representation Number of Bipartite Graphs using Neighborhood Graphs”, arXiv:2311.13980 (2023).

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.