Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 62 — Erdős Problems

Problem 62

If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$ ) which is a subgraph of both $G_1$ and $G_2$ ?

Source: erdosproblems.com/62

Graph theory

Wiki page

Status

Open

No claim settles this problem.

EHS74: Erdős, P. and Hajnal, A. and Shelah, S., On some general properties of chromatic numbers. Topics in topology (Proc. Colloq., Keszthely, 1972) (1974), 243-255.
Er87: Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 61 NextProblem 63

On this page

Statement
Status
References
Proof claims
Discussion

Status: Open
Topics: Graph theory
In the wiki: Wiki page