# P3142: The Total Coloring Conjecture

- ID: `P3142`
- Reference: `total-coloring-conjecture`
- Page: https://theoremdb.org/statements/P3142
- Record maturity: Reviewed problem with recorded work

## Problem

For every finite simple graph \(G\) with maximum degree \(\Delta(G)\), is its total chromatic number \(\chi_T(G)\) at most \(\Delta(G)+2\)?

### Context

Known frontier: Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion.

Open boundary: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 preprint claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. A repository corpus search returned no duplicate target.

### Problem setup

- **Definition (total coloring).** A coloring of the vertices and edges in which adjacent vertices, adjacent edges, and incident vertex-edge pairs receive different colors.
- **Definition (total chromatic number).** The minimum number χ_T(G) of colors required by a total coloring of G.
- **Definition (maximum degree).** Δ(G) is the largest degree of a vertex of G.
- **Remark.** A total coloring colors the vertices and edges together. Adjacent vertices, adjacent edges, and every incident vertex-edge pair must receive different colors. A maximum-degree vertex and its incident edges already require Δ(G)+1 colors. The conjecture says one additional color always suffices.

### What counts as a solution

- Prove χ_T(G) ≤ Δ(G)+2 for every finite simple graph G.
- Or give an explicit finite simple graph G and a rigorous lower-bound certificate showing χ_T(G) ≥ Δ(G)+3.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion. Exact unresolved remainder: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target. [1](#reference-1) [2](#reference-2) [3](#reference-3)

## 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 graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion. Exact unresolved remainder: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion.

The exact unresolved remainder is: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target.

A complete resolution must meet the following acceptance conditions:
- Prove χ_T(G) ≤ Δ(G)+2 for every finite simple graph G.
- Or give an explicit finite simple graph G and a rigorous lower-bound certificate showing χ_T(G) ≥ Δ(G)+3.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion. Exact unresolved remainder: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target.
- The release review checked 3 structured sources on 2026-08-01.
- Equivalent-formulation queries: Total Coloring Conjecture Delta plus 2 general graph open 2026; total coloring large minimum degree 2025; total chromatic number Delta plus 2 conjecture
- Strongest checked neighboring result: Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion.
- Exact unresolved remainder: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target.

### Other known results

- **Claim 2** (supported): Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion. [1](#reference-1) [2](#reference-2) [3](#reference-3)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Every graph satisfies χ_T(G) ≤ Δ(G)+2⌈n/(Δ(G)+1)⌉. The conjectured Δ(G)+2 bound holds for sufficiently large graphs whose minimum degree exceeds half their order by a fixed proportion. Unresolved remainder: Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target. [1](#reference-1) [2](#reference-2) [3](#reference-3)

### Open directions

- **Route 2** (reported): Remove all density and structural assumptions and prove the Δ(G)+2 bound for every finite simple graph, or find a graph requiring Δ(G)+3 colors. A 2020 arXiv manuscript claims a proof, while subsequent peer-reviewed papers continue to treat the unrestricted statement as open. TheoremDB corpus searches returned no duplicate target.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `total-coloring-conjecture`, 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>Aseem Dalal, Jessica McDonald, and Songling Shan, “Total Coloring Graphs With Large Maximum Degree”. Journal of Graph Theory 110(3) (2025), 249-262. DOI 10.1002/jgt.23268. Abstract and main theorems https://doi.org/10.1002/jgt.23268
   - Also cited at A. Dalal, J. McDonald, and S. Shan, Total Coloring Graphs With Large Maximum Degree, Journal of Graph Theory 110(3) (2025), 249-262. Abstract and main theorems
   - journal_article; primary source; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2405.07382
   - Source use: original_summary
   - Proves χ_T(G) ≤ Δ(G)+2⌈|V(G)|/(Δ(G)+1)⌉ for every finite simple graph and verifies the conjectured bound for sufficiently large dense regular graphs.
   - Source used to assess the problem's recorded status.
   - For The Total Coloring Conjecture: This is the dated publication status for the canonical target The Total Coloring Conjecture.
   - Source named by the research packet.
2. <a id="reference-2"></a>Henderschedt, Owen, McDonald, Jessica, and Shan, Songling, “Total coloring graphs with large minimum degree”. arXiv (2025). DOI 10.48550/arXiv.2507.05548. Abstract and main theorem https://doi.org/10.48550/arXiv.2507.05548
   - preprint; primary source; arXiv:2507.05548, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2507.05548
   - Source use: original_summary
   - Proves that for every ε>0, all sufficiently large n-vertex graphs with minimum degree at least (1+ε)n/2 satisfy χ_T(G) ≤ Δ(G)+2.
   - Source used to assess the problem's recorded status.
   - For The Total Coloring Conjecture: Proves that for every ε>0, all sufficiently large n-vertex graphs with minimum degree at least (1+ε)n/2 satisfy χ_T(G) ≤ Δ(G)+2.
3. <a id="reference-3"></a>E. W. Weisstein, Total Chromatic Number, MathWorld, Wolfram Research. mathworld.wolfram.com checked 2026-08-01. Definition, lower bound, and displayed Total Coloring Conjecture https://mathworld.wolfram.com/TotalChromaticNumber.html
   - reference_database; primary source; checked 2026-08-01
   - Source use: original_summary
   - Gives the standard total-coloring definition, the lower bound Δ(G)+1, the conjectured upper bound Δ(G)+2, and the original Behzad and Vizing attributions.
   - Source used to assess the problem's recorded status.
   - For The Total Coloring Conjecture: Gives the standard total-coloring definition, the lower bound Δ(G)+1, the conjectured upper bound Δ(G)+2, and the original Behzad and Vizing attributions.