[#P3084] A common high-chromatic subgraph of two ℵ_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\).

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.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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

Saved packet · August 1, 2026

What counts as a solution

Saved packet 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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

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

All 3 recorded relations between these records and the problem

2See also

A period-six recurrence for domination on the three-row knight graphgraph theory
Leaf complexity of six-vertex graph connectivitygraph theory
Exact Hamiltonicity probability on eight labeled verticesgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“A common high-chromatic subgraph of two \(\aleph_1\)-chromatic graphs.” TheoremDB. P3084. Problem statement; statement text SHA-256 997c690cbfdd4b7c35d011413d0f5657c8e46c7a5e8d0299449e45a61d4fc061. https://theoremdb.org/statement/?ref=P3084

BibTeX

@misc{theoremdb-problem-997c690cbfdd4b7c35d011413d0f5657c8e46c7a5e8d0299449e45a61d4fc061,
  title = {{A common high-chromatic subgraph of two \textbackslash{}(\textbackslash{}aleph\_1\textbackslash{})-chromatic graphs}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 997c690cbfdd4b7c35d011413d0f5657c8e46c7a5e8d0299449e45a61d4fc061},
  url = {https://theoremdb.org/statement/?ref=P3084}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance