Bouchard–Hertz–Desaulniers deficiency bound for graphs
Bouchard–Hertz–Desaulniers deficiency bound for graphs
Let be a graph, let denote its vertex set, and let denote its deficiency.
Bouchard–Hertz–Desaulniers conjecture. For every graph ,
The conjecture is still open, but it holds for regular graphs, some bipartite graphs, and outerplanar graphs. If true, it would imply upper bounds for the deficiency of triangle-free graphs and of graphs with at least three vertices.
Sources & referencesView supporting material
Primary source
Petros A. Petrosyan and Hrant H. Khachatrian, “Further results on the deficiency of graphs”, arXiv:1608.00904 (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.