Minimal-clique-cover conjecture for realizable graphs

Let HH be a realizable graph. A clique cover of HH is a collection of cliques whose union covers all edges of HH, and let nn be the smallest number of cliques in such a cover. Minimal-clique-cover conjecture. There is always a digraph GG realizing HH with

VG=n.|V_G|=n.

Equivalently, the theorem characterizing realizability continues to hold when the number of cliques is required to be minimal. This would make the decidability algorithm substantially more efficient by restricting the search to minimum-size clique covers; the source gives no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

J. Fromentin, P. -L Giscard and T. Karaboghossian, “Realizable cycle structures in digraphs”, arXiv:2110.15618 (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.