Erdős problem 596 · problems.science

Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs $(G_1, G_2)$ is it true that

Sources

Browse retained paths and inspect the exact material available for this Problem.

9 retained statements2415f78e850a

FormalConjectures/ErdosProblems/

596.lean

Retained formal statement7 of 9

Whether $(K_4, K_3)$ is Erdős–Hajnal exceptional is precisely the content of Erdős Problem 595. The finite Ramsey property holds (Folkman 1970, Nešetřil–Rödl [NeRo75]); the open part is whether every $K_4$ -free graph is a countable union of triangle-free graphs.

FormalConjectures/ErdosProblems/596.leanErdos596.erdos_596.variants.K4_K3_exceptional_iff1 lineExact file

1True ↔ (SimpleGraph.completeGraph (Fin 4)).IsErdosHajnalExceptional (SimpleGraph.completeGraph (Fin 3))

OpenStatement only, no proof

Sources

Search problems.science