The bipartiteness conjecture for Cheeger graphs

Let GG be a Cheeger graph, meaning a graph attaining the first Cheeger constant of the relevant simplex. Bipartiteness conjecture. All Cheeger graphs are bipartite. This is proposed as a stronger statement than the conjecture that all Cheeger graphs are triangle-free. It is presented as an open problem.

Sources & referencesView supporting material

Primary source

D. N. Kozlov, “The first Cheeger constant of a simplex”, arXiv:1610.07136 (2017).

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.