The Erdős–Goodman–Pósa conjecture for graphs with independence number at most two

About 4 years old · traced to

Let GG be a graph, and let α(G)\alpha(G) denote its independence number. A clique cover of GG is a collection of cliques whose union of covered edges contains every edge of GG.

Erdős–Goodman–Pósa conjecture. If

α(G)≤2,\alpha(G)\le 2,

then GG has a clique cover of size at most ∣G∣|G|.

This is described as a long-standing conjecture, but the source does not identify its origin. Its status is therefore recorded as open.

References

Primary source

Tung Nguyen, Alex Scott, Paul Seymour and Stephan Thomasse, “Clique covers of H-free graphs”, arXiv:2211.12065 (2022).

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.