The Erdős–Goodman–Pósa conjecture for graphs with independence number at most two
The Erdős–Goodman–Pósa conjecture for graphs with independence number at most two
Let be a graph, and let denote its independence number. A clique cover of is a collection of cliques whose union of covered edges contains every edge of .
Erdős–Goodman–Pósa conjecture. If
then has a clique cover of size at most .
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
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.