The triangle-freeness conjecture for Cheeger graphs
The triangle-freeness conjecture for Cheeger graphs
Let be a Cheeger graph, meaning a graph attaining the first Cheeger constant of the relevant simplex. Triangle-freeness conjecture. All Cheeger graphs are triangle-free. This is motivated by the authors' examples, in which an optimal graph's Cheeger constant receives no contribution from a triangle whose three edges all belong to the graph. The conjecture 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
Sign in to submit a solution.
No solutions have been posted yet.