The edge clique cover conjecture for graphs with independence number two

From papers

Let GG be a simple graph with nn vertices. A clique is a set of vertices inducing a complete graph, and the edge clique cover number ecc(G)ecc(G) is the minimum number of cliques such that both endpoints of every edge lie in at least one of them. Write balpha(G)balpha(G) for the independence number of GG. Edge clique cover conjecture. If

α(G)=2,\alpha(G)=2,

then

ecc(G)n.ecc(G)\leq n.

This conjecture is a special case of the question whether every claw-free graph satisfies ecc(G)necc(G)\leq n. Positive results were known for claw-free graphs with independence number greater than two, leaving the case α(G)=2\alpha(G)=2 as the conjectural case considered here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Frank Ramamonjisoa, “Edge Clique Covers in Graphs with Independence Number Two: a Special Case”, arXiv:2112.03961 (2021).

Solutions 0

No solutions have been posted yet.