The crown-subgraph conjecture for representation numbers of bipartite graphs

About 3 years old · traced to

Let GG be a bipartite graph. For κ0≥5 \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.

References

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.