[#P3084] A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs

Neutral schematic of two infinite graph clouds sharing a finite highlighted four-chromatic pattern. — The objects and operations appearing in A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs.

Problem. For any two simple graphs \(G_1,G_2\), each with chromatic number \(\aleph_1\), must there exist a simple graph \(H\) that is isomorphic to a subgraph of both \(G_1\) and \(G_2\) and has chromatic number at least \(4\)? Determine also whether \(H\) can always be required to have chromatic number \(\aleph_0\).

1Context

Known frontier: Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. Open boundary: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.

2Problem setup

Definition 1 (Chromatic number \(\aleph_1\)). The least cardinality of a proper vertex-colour set is the first uncountable cardinal.

Definition 2 (Common subgraph). The graph \(H\) admits injective adjacency-preserving embeddings into both \(G_1\) and \(G_2\); inducedness is not required.

Remark 1. All sufficiently large odd cycles occur in every \(\aleph_1\)-chromatic graph, giving common chromatic number three.

3What counts as a solution

Prove the existence of a common \(4\)-chromatic subgraph for every pair, or construct a pair with no such common subgraph.
Resolve separately the stronger \(\aleph_0\)-chromatic version.

1Status

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. Exact unresolved remainder: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.^[1][2]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. Exact unresolved remainder: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.^[1][2] Relevance to this problem This is the dated publication status for the canonical target A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. The exact unresolved remainder is: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger. A complete resolution must meet the following acceptance conditions: - Prove the existence of a common \(4\)-chromatic subgraph for every pair, or construct a pair with no such common subgraph. - Resolve separately the stronger \(\aleph_0\)-chromatic version. Open full record →
	Result	Supported
claim · Claim 2 Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed.^[1][2] Relevance to this problem Locates the present research frontier immediately below A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. This leaves the following boundary unresolved: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there.^[1][2] Relevance to this problem Documents why A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across source collection and its cited primary literature, Crossref/arXiv or MathSciNet stable records, TheoremDB published, prospecting, formal-conjecture, packet, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - "Erdős Problem #62" common subgraph - two graphs chromatic number aleph_1 common subgraph chromatic 4 - common chromatic subgraph aleph one 2025 2026 The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 The first unknown guaranteed chromatic number is four; the countably infinite target is stronger. Relevance to this problem Turns the remaining uncertainty in A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Prove the existence of a common \(4\)-chromatic subgraph for every pair, or construct a pair with no such common subgraph. - Resolve separately the stronger \(\aleph_0\)-chromatic version. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. Exact unresolved remainder: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.

Equivalent-formulation queries: "Erdős Problem #62" common subgraph; two graphs chromatic number aleph_1 common subgraph chromatic 4; common chromatic subgraph aleph one 2025 2026
Strongest checked neighboring result: Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed.
Exact unresolved remainder: The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.

How the 4 records connectTyped relations and evidence flow

ProblemA common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Cycle Double Cover Conjecturegraph theory
Is there a truly subcubic algorithm for weighted APSP?graph theory
The Total Coloring Conjecturegraph theory

How to cite

TheoremDB contributors, “A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/common-chromatic-subgraph-aleph-one

This page as plain text: common-chromatic-subgraph-aleph-one.md

This problem includes 4 records joined by 3 typed links, sourced from erdosproblems.com^[1], current as of August 1, 2026.

1References

Packet source. Thomas F. Bloom, Erdős Problem #62, Erdős Problems database (living entry), accessed 2026-08-01. Problem #62, OPEN banner, statement, remarks, and bibliography. Problem #62, OPEN banner, statement, remarks, and bibliography. ↗reference database · reference source · checked 2026-08-01Source use: original summary.Supplies the maintained formulation, current open-status assessment, and recorded partial results.Also cited at Thomas F. Bloom, Erdős Problem #62, Erdős Problems database (living entry), accessed 2026-08-01. Problem #62, OPEN banner, statement, remarks, and bibliography.Source used to assess the problem's recorded status.For A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs: This is the dated publication status for the canonical target A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs.Source named by the research packet.
P. Erdős, “Some problems on finite and infinite graphs,” Logic and Combinatorics (Arcata, 1985), Contemporary Mathematics 65 (1987), 223–228. Common-subgraph question for uncountably chromatic graphs. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Records an original formulation or early published statement of the problem.Source used to assess the problem's recorded status.For A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs: Records an original formulation or early published statement of the problem.

Original TheoremDB statement and summary based on citation-only scholarly sources; no source prose, proof, table, code, or figure is reproduced.

[#P3084] A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance