ProofAtlas

Graph coloring

Total Coloring Conjecture

Collaboration beta

Can every finite simple graph have its vertices and edges colored together using at most two more colors than its maximum degree? The packet narrows one internal branch to twelve explicit marked configurations, but it neither colors those configurations nor proves the conjecture in general.

χ''(G)≤Δ(G)+2
Known results and sources
An exact properly total-colored five-cycle uses cream, gold, teal, and rust beside twelve faint 4×4 marked-C5 matrix normal forms labeled R1 through R12 on a dark green field.
A five-cycle illustrates the joint vertex-edge constraint; the conjecture asks whether every graph admits a total coloring within the universal bound.

Research problem

Exact mathematical statement

For every finite simple graph GG, its total chromatic number satisfies

χ''(G)≤Δ(G)+2.\chi''(G) \le \Delta(G)+2.

A total coloring assigns colors to every vertex and edge so that adjacent vertices, adjacent edges, and incident vertex-edge pairs receive different colors. The source contains neither a proof of this universal statement nor a counterexample.

Problem infographic

Problem at a glance

A wide diagram shows an exact properly total-colored five-cycle using four colors, meeting its Delta-plus-two bound with adjacent vertices, adjacent edges, and incident vertex-edge pairs all different, beside a separate marked branch of twelve dim unresolved graph tiles.
Problem first: color vertices and edges together within the conjectured bound; the packet's twelve-form branch remains a separate, incomplete obligation.

Current mathematical picture

Where work on Total Coloring Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureThirteen-form marked-C5 catalog

The source gives matrices A=0001000101101010 and B=0001001000111100 and states B^T=A under an allowed reflection. The corrected twelve-form finite coloring problem and broader structural routes remain viable as source-reported research directions.

Route status · Narrowed route
Main reductionCurrent reduction

One active internal branch reduces a marked shortest-C5 complement profile at r=10 to twelve matrix-orbit representatives reconstructed as 27-vertex 10-regular triangle-free graphs.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeProduce a verifiable total 18-coloring certificate for every one of the twelve retained complements.Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Total Coloring Conjecture in numbers

4kretained lines of mathematical investigation3,960 in the current working snapshot
Argument development
3,196 · 81%
Explored or eliminated routes
161 · 4%
Computational analysis
88 · 2%
Open obligations
167 · 4%
Definitions and setup
348 · 9%
7selected mapped statements2routes investigated3open questions3contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byMehdi Behzad, Vadim G. VizingProposed1965Status checkedAug 14, 2026
Source recordedAug 14, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

12 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

12 selected steps

Scroll horizontally to explore the route

Working route overview for Total Coloring ConjectureA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Color all vertices and edges with at most Delta(G)+2 colors. — Depends on missing premiseColor all vertices and edgeswith at most Delta(G)+2colors.Current reduction — Depends on missing premiseCurrent reductionClosing target — Depends on missing premiseClosing targetDegree-four case — Depends on missing premiseDegree-four caseMarked-cycle scope — Depends on missing premiseMarked-cycle scopeReconstructed complements — Depends on missing premiseReconstructed complementsTwelve marked orbits — Depends on missing premiseTwelve marked orbitsThirteen-form marked-C5 catalog — stoppedThirteen-form marked-C5catalogPromoting closure of the marked branch to the full conjecture — stoppedPromoting closure of themarked branch to the fullconjectureProduce a verifiable total 18-coloring certificate for every one of the twelve retained complements. — OpenProduce a verifiable total18-coloring certificate forevery…Prove a degree-preserving two-switch or other transport lemma that validly connects the retained forms. — OpenProve a degree-preservingtwo-switch or othertransport…Keep the local marked-C5 closure separate from a universal proof of the Total Coloring Conjecture. — OpenKeep the local marked-C5closure separate from auniversal…
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded
Narrowed routeThirteen-form marked-C5 catalog

The source gives matrices A=0001000101101010 and B=0001001000111100 and states B^T=A under an allowed reflection. The corrected twelve-form finite coloring problem and broader structural routes remain viable as source-reported research directions.

Route status · Narrowed route
Narrowed routePromoting closure of the marked branch to the full conjecture

The trust-boundary section explicitly lists that implication among the claims not made. Treat the finite branch as one local obligation while retaining the universal mechanism as a separate open dependency.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks
01
Produce a verifiable total 18-coloring certificate for every one of the twelve retained complements.Suggested move: Start with one catalog row and record a complete vertex-and-edge assignment that an independent checker can replay.
Ready to work on
02
Prove a degree-preserving two-switch or other transport lemma that validly connects the retained forms.Suggested move: State exact hypotheses, track every incidence conflict, and reduce only after demonstrating certificate transport.
Ready to work on
03
Keep the local marked-C5 closure separate from a universal proof of the Total Coloring Conjecture.Suggested move: Maintain a dependency ledger showing which global graph families and structural branches remain outside this reduction.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 14, 2026
Current statusOpen conjecture

The universal bound remains open. Peer-reviewed and recent preprint sources continue to prove the conjecture for scoped graph classes or degree regimes; none of the sources in this current pass reports a recognized universal resolution.

[1][2][3]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. PreprintKardoš and Matok classified optimal total coloring for cubic and subcubic Halin graphs, a scoped family result.[3]
  2. Peer reviewedDalal, McDonald, and Shan proved improved general bounds and confirmed the conjecture for a stated regime of regular graphs with sufficiently large maximum degree relative to order.[2]
  3. Peer reviewedA peer-reviewed survey synthesized post-1995 progress and stated that the conjecture remained unsettled even for planar graphs.[1]
3 cited sources2 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusTotal Coloring Conjecture
Solved special caseSubcubic and cubic Halin graphs

Subcubic graphs satisfy the conjectured five-color upper bound, and the cited preprint resolves the sharper four-versus-five question for Halin graphs.

[3]
Solved special caseRegular graphs in a large-maximum-degree regime

The conjectured bound is confirmed for the paper's large-degree regular-graph regime, not for arbitrary finite simple graphs.

[2]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA formal statement library for total vertex-edge coloring and total chromatic number
  • Formalization targetMachine-checked imports for the major established special classes and asymptotic bounds
  • Formalization targetA statement-aligned certificate format for finite total-coloring assignments

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Cited passages corrected

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements3 open questions2 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction1 of 71
  • lemma2 of 72
  • computational claim2 of 72
  • negative result1 of 71
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included
  • retained route statementColor all vertices and edges with at most Delta(G)+2 colors.
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementDegree-four caseintermediate
  • retained route statementTwelve marked orbitsintermediate
  • retained route statementReconstructed complementsintermediate
  • retained route statementMarked-cycle scopeintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureThirteen-form marked-C5 catalogreported failure
  • Useful failurePromoting closure of the marked branch to the full conjecturereported failure
  • Research targetProduce a verifiable total 18-coloring certificate for every one of the twelve retained complements.open
  • Research targetProve a degree-preserving two-switch or other transport lemma that validly connects the retained forms.open
  • Research targetKeep the local marked-C5 closure separate from a universal proof of the Total Coloring Conjecture.open
  • Research targetFinite coloring frontiersuperseded
  • Research targetUniversal mechanism still missingsuperseded
  • ComputationThe current work reports exhaustive enumeration of all 2^16 binary matrices under constrained degree sequences and its stated symmetry action.The reported category orbit counts are 2, 3, 1, 2, and 4, totaling twelve; no packet attachment was run by ProofAtlas. · reported unreproduced
  • Narrowed routeThirteen-form marked-C5 catalogThe source gives matrices A=0001000101101010 and B=0001001000111100 and states B^T=A under an allowed reflection. The corrected twelve-form finite coloring problem and broader structural routes remain viable as source-reported research directions.
  • Narrowed routePromoting closure of the marked branch to the full conjectureThe trust-boundary section explicitly lists that implication among the claims not made. Treat the finite branch as one local obligation while retaining the universal mechanism as a separate open dependency.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeProduce a verifiable total 18-coloring certificate for every one of the twelve retained complements.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointProduce a verifiable total 18-coloring certificate for every one of the twelve retained complements.

Total Coloring Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Can every finite simple graph have its vertices and edges colored together using at most two more colors than its maximum degree? The current work narrows one internal branch to twelve explicit marked configurations, but it neither colors those configurations nor proves the conjecture in general.

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references3 cited works · next context review by Nov 14, 2026

The mathematical context was checked on Aug 14, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Total colorings—a surveysurvey or monograph · Jayabalan Geetha, Narayanan Narayanan, Kanagasabapathi Somasundaram · Taylor & Francis · 2023-03-08 · DOI 10.1080/09728600.2023.2187960 · accessed Aug 14, 2026
  2. 2
    Total Coloring Graphs With Large Maximum Degreepeer reviewed result · Aseem Dalal, Jessica McDonald, Songling Shan · Journal of Graph Theory · 2025-06-11 · DOI 10.1002/jgt.23268 · accessed Aug 14, 2026
  3. 3
    Total coloring of (sub)cubic Halin graphspreprint · František Kardoš, Matúš Matok · arXiv · 2026-03-24 · ARXIV 2603.23189 · accessed Aug 14, 2026

Important qualifications

  • Scoped primary and publisher-hosted status pass, not a systematic literature review.
  • Recent subclass results do not imply the universal conjecture.
  • No submitted packet URL was fetched and no unreviewed general-proof claim was promoted.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image