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

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.

Sources & referencesView supporting material

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.