[#P3142] The Total Coloring Conjecture

A graph with colored vertices and edges using a shared palette. — A structural graph diagram of the statement's mathematical objects.

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\)?

1Context

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.

2Problem setup

Definition 1 (total coloring). A coloring of the vertices and edges in which adjacent vertices, adjacent edges, and incident vertex-edge pairs receive different colors.

Definition 2 (total chromatic number). The minimum number χ_T(G) of colors required by a total coloring of G.

Definition 3 (maximum degree). Δ(G) is the largest degree of a vertex of G.

Remark 1. 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.

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

1Status

Current status (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.^[1][2][3]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 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][2][3] Relevance to this problem This is the dated publication status for the canonical target The Total Coloring Conjecture. 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, Reference 3 Details 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. Open full record →
	Result	Supported
claim · Claim 2 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][2][3] Relevance to this problem Locates the present research frontier immediately below The Total Coloring Conjecture. 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, Reference 3 Details 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. This leaves the following boundary unresolved: 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 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 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][2][3] Relevance to this problem Documents why The Total Coloring Conjecture 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, Reference 3 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - Total Coloring Conjecture Delta plus 2 general graph open 2026 - total coloring large minimum degree 2025 - total chromatic number Delta plus 2 conjecture 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. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 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. Relevance to this problem Turns the remaining uncertainty in The Total Coloring Conjecture 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: 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 claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - 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. 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 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.

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.

How the 4 records connectTyped relations and evidence flow

ProblemThe Total Coloring Conjecture

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 Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics
Ryser’s conjecture for multipartite hypergraphscombinatorics

How to cite

TheoremDB contributors, “The Total Coloring Conjecture,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/total-coloring-conjecture

This page as plain text: total-coloring-conjecture.md

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

1References

Packet source. 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. ↗ open copy ↗journal article · primary source · checked 2026-08-01Source 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.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.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.
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. ↗ open copy ↗preprint · primary source · arXiv:2507.05548, checked 2026-08-01 · checked 2026-08-01Source 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.
E. W. Weisstein, Total Chromatic Number, MathWorld, Wolfram Research. mathworld.wolfram.com checked 2026-08-01. Definition, lower bound, and displayed Total Coloring Conjecture. ↗reference database · primary source · checked 2026-08-01Source 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.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3142] The Total Coloring Conjecture

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