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 statement9 of 9

The original Erdős–Hajnal conjecture (that no exceptional pair exists) is false — witnessed by $(C_4, C_6)$ via C4_C6_is_exceptional.

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

1False ↔ ∀ {U₁ U₂ : Type} (G₁ : SimpleGraph U₁) (G₂ : SimpleGraph U₂), ¬G₁.IsErdosHajnalExceptional G₂

SolvedStatement only, no proof