The Erdős–Hajnal conjecture

Show that graphs avoiding a fixed induced subgraph H always contain a clique or independent set of size n^{c(H)}.

shoal File it in the catalog (shoal-catalog 0521c19bbd38) 6a9b818 · 2周前历史

23 行 · 449 Bytes 原始文件永久链接历史

1	{
2	"domain": "mathematics",
3	"topics": [
4	"graph-theory",
5	"combinatorics"
6	],
7	"type": "proof",
8	"cover": {
9	"motif": "graph",
10	"n": 5
11	},
12	"source": {
13	"key": "erdos",
14	"name": "Erdős Problems",
15	"url": "https://www.erdosproblems.com/61",
16	"id": "61",
17	"curator": "Thomas Bloom",
18	"poser": "Paul Erdős and András Hajnal",
19	"status": "open",
20	"as_of": "2026-10-20",
21	"catalog": "0521c19bbd38"
22	}
23	}