Minimal-clique-cover conjecture for realizable graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.