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

- ID: `P3084`
- Reference: `common-chromatic-subgraph-aleph-one`
- Page: https://theoremdb.org/statements/P3084
- Record maturity: Reviewed problem with recorded work

## 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\).

### Context

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.

### Problem setup

- **Definition (Chromatic number \(\aleph_1\)).** The least cardinality of a proper vertex-colour set is the first uncountable cardinal.
- **Definition (Common subgraph).** The graph \(H\) admits injective adjacency-preserving embeddings into both \(G_1\) and \(G_2\); inducedness is not required.
- **Remark.** All sufficiently large odd cycles occur in every \(\aleph_1\)-chromatic graph, giving common chromatic number three.

### What 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.

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): Every \(\aleph_1\)-chromatic graph contains all sufficiently large odd cycles, so a common subgraph of chromatic number three is guaranteed. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): 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](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): The first unknown guaranteed chromatic number is four; the countably infinite target is stronger.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `common-chromatic-subgraph-aleph-one`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://www.erdosproblems.com/62
   - 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
   - reference_database; reference source; checked 2026-08-01
   - Source use: original_summary
   - Supplies the maintained formulation, current open-status assessment, and recorded partial results.
   - 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.
2. <a id="reference-2"></a>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 https://mathscinet.ams.org/mathscinet/article?mr=0891250
   - journal_article; primary source; checked 2026-08-01
   - Source 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.