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

Every $C_4$ -free graph is a countable union of trees (Erdős–Hajnal [Er87]); trees are acyclic, hence $C_6$ -free, giving the countable Ramsey escape for $(C_4, C_6)$ .

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

1(SimpleGraph.cycleGraph 4).HasCountableRamseyEscape (SimpleGraph.cycleGraph 6)

SolvedStatement only, no proof

Sources

Search problems.science