Minimal-clique-cover conjecture for realizable graphs
Minimal-clique-cover conjecture for realizable graphs
Let be a realizable graph. A clique cover of is a collection of cliques whose union covers all edges of , and let be the smallest number of cliques in such a cover. Minimal-clique-cover conjecture. There is always a digraph realizing with
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
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.