gpt 6 astra ultra attempt on Math-1090

List Total Colouring Conjecture

Definitions and mathematical statement

Let $H$ be a finite loopless multigraph; parallel edges are distinct elements. Its total graph $T(H)$ is a simple graph on the disjoint union $V(H)\sqcup E(H)$. Two distinct vertex-elements are adjacent when joined by an edge of $H$; two distinct edge-elements are adjacent when their edges share an endpoint; a vertex-element and an edge-element are adjacent when incident in $H$.

A proper colouring of $T(H)$ therefore colours both vertices and edges of $H$, separating adjacent vertices, incident edges, and every vertex from each incident edge. Let $\chi(T(H))$ be the minimum common palette size. For a simple graph $F$, a list assignment gives each vertex $x$ a finite set $L(x)$ of allowed colours. A proper list colouring chooses $c(x)\in L(x)$ with different choices at adjacent vertices. The list chromatic number $\chi_\ell(F)$ is the least integer $q$ for which every assignment with $|L(x)|\geq q$ admits such a colouring.

The List Total Colouring Conjecture states \[ \chi_\ell(T(H))=\chi(T(H)) \qquad\text{for every finite loopless multigraph }H. \] Thus arbitrary separate lists for all vertices and edges should suffice whenever their sizes equal the ordinary total chromatic number. The lists may overlap in any way and need not come from one palette of that size. The inequality $\chi_\ell\geq\chi$ is automatic from identical lists; the reverse inequality is the target.

Short English statement

Do arbitrary colour lists of ordinary total-colouring size always suffice to colour every vertex and edge of a loopless multigraph?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

A material literature update.

The catalogue's historical conjecture must not be read as a verified current open-status claim. Noel's primary preprint [S3], version 1 submitted 29 September 2026, reports a simple cubic graph on twenty vertices with ordinary total chromatic number four and list total chromatic number five, disproving the displayed equality. We retain the original statement for catalogue identity. This attempt independently proves the forest case and checks the reported example's ordinary four-colouring; it does not independently reproduce the full non-list-colourability proof.

A complete theorem for forests.

Let $H$ be a nonempty forest and put $\Delta=\Delta(H)$. If $H$ has at least one edge, then \[ \chi_\ell(T(H))=\chi(T(H))=\max\{\Delta+1,3\}. \tag{1} \] If $H$ is edgeless, both numbers are one. For the lower bound in $1$, a maximum-degree vertex together with its incident edge-elements forms a clique of order $\Delta+1$ in the total graph. Also, the two endpoints and the edge-element of any edge form a triangle, so three colours are necessary even when $\Delta=1$. These lower bounds apply to list chromatic number as well, by assigning every element the same palette.

For the upper bound put $q=\max\{\Delta+1,3\}$. We construct a deletion order of the elements of $T(H)$ in which each deleted element has at most $q-1$ surviving neighbours, all mutually adjacent. Choose a leaf $v$ of $H$ with neighbour $u$, and write $e=uv$. Delete the vertex-element $v$ first. Its surviving neighbours are exactly $u$ and the edge-element $e$, and these are adjacent. Delete $e$ next. Its surviving neighbours are the vertex-element $u$ and the other edge-elements incident to $u$. They form a clique and number exactly $d_H(u)\le\Delta$. The remaining total graph is exactly $T(H-v)$: no unwanted adjacency disappears or is inserted among the surviving elements. Repeat, deleting isolated vertex-elements whenever necessary.

Now give every element an arbitrary list of at least $q$ colours. Colour in reverse deletion order. At each step at most $q-1$ neighbours already have colours, so at most $q-1$ colours are forbidden from that element's list; at least one allowed colour remains. This is valid even if different elements have unrelated lists. It proves $\chi_\ell(T(H))\le q$, completing $1$. The clique property of the deletion order is stronger than needed for this greedy argument, but makes the total-graph structure transparent.

What is checked in the new counterexample.

The reported construction [S3] joins four disjoint copies of $K_{2,3}$, one cross edge between each pair of copies using their distinct degree-two terminals. The companion script reconstructs these twenty vertices and thirty edges and checks the paper's explicit four-colouring on all fifty vertex- and edge-elements. A cubic vertex and its incident edges give the matching lower bound four. The separate claim that a specified assignment of four-element lists has no total colouring is taken from [S3], not inferred from this ordinary-colouring certificate.

Why the forest proof stops.

The deletion step uses a vertex with exactly one incident edge. In a cubic graph every vertex-element instead has six neighbours in its total graph: three adjacent vertex-elements and three incident edge-elements. With four-element lists, naive greedy insertion can therefore have every available colour blocked. More importantly, there need not be a leaf to start the exact reduction $T(H)\to T(H-v)$. An ordinary four-colouring only checks one common palette assignment. It cannot certify the universal quantifier over all four-element lists, which is the quantifier the reported example defeats.

The script scripts/check_attempt_batch02_graphs_2026_10_01.py also generates all labelled trees through five vertices, constructs their total graphs, and verifies the leaf-pair deletion bound in the proof. These checks include the single-edge case requiring three colours rather than $\Delta+1=2$.

Final status and remaining verification.

The forest equality is proved and the ordinary-colouring side of the reported example is independently checked. The historical universal conjecture is reported disproved in [S3], not asserted open here. This attempt's independent reproduction of that full disproof is UNRESOLVED: the remaining task would be to verify the incompatible four-list assignment, rather than seek a proof of the superseded universal equality.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3195 (OPG-56449), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, List Total Colouring Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/list_total_colouring_conjecture.
• S3 Jonathan A. Noel, The List Total Colouring Conjecture is False, arXiv:2609.38417v1, submitted 29 September 2026. Primary reported counterexample and explicit total colouring; the full list obstruction is not independently reproduced in this attempt. https://arxiv.org/html/2609.38417v1.