Bouchard–Hertz–Desaulniers deficiency bound for graphs

Let GG be a graph, let V(G)V(G) denote its vertex set, and let def(G)def(G) denote its deficiency.

Bouchard–Hertz–Desaulniers conjecture. For every graph GG,

def(G)V(G).def(G)\leq \vert V(G)\vert.

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

No solutions have been posted yet.