gpt 6 astra ultra attempt on Math-1106

Acyclic list colouring of planar graphs.

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple planar graph. A list assignment gives each vertex $v$ a finite set $L(v)$ of permitted colours. An $L$-colouring is a map $c:V\to\bigcup_vL(v)$ satisfying $c(v)\in L(v)$ for every vertex. It is proper when adjacent vertices receive different colours.

A proper colouring is acyclic if there is no cycle using only two colours. Equivalently, for every two distinct colour names $a,b$, the induced subgraph on $c^{-1}(\{a,b\})$ is a forest, meaning that it has no undirected cycle. This condition permits cycles using three or more colours. Say that $G$ is acyclically $k$-choosable if every assignment with $|L(v)|=k$ for all $v$ admits an acyclic proper $L$-colouring.

The conjecture is that every finite simple planar graph is acyclically five-choosable. Written with all quantifiers, for every such $G$ and every family of five-element lists $\{L(v):v\in V\}$, there exists a map $c$ from those lists which is proper and for which each cycle has at least three distinct colours among its vertices.

Lists are arbitrary and may overlap in any way; their union need not have size five. Thus a colouring from one common five-colour palette would establish only the ordinary acyclic-colouring assertion. Likewise, a proper list-colouring without the condition on two-coloured cycles would not establish this conjecture. Lists larger than five are equivalent for this purpose, since one may first retain any five colours per vertex.

Short English statement

Can every planar graph be coloured from arbitrary lists of five colours so that every cycle uses at least three colours?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Literature and scope.

The original attribution in [S2] is to Borodin, Fon-Der-Flaass, Kostochka, Raspaud and Sopena. The primary paper by Postle, Smith-Roberge and Vicenzo [R1] distinguishes ordinary acyclic five-colouring of planar graphs, acyclic seven-list-colouring of planar graphs, and its own nine-list result for locally planar graphs. None of those statements automatically gives arbitrary five-element lists here. We prove two constructive list-colouring subcases and a sharp lower-bound example showing that four colours could not replace five in the proposed theorem.

A sufficient elimination order.

Suppose the vertices of a graph are ordered $v_1,\ldots,v_n$ so that, for each $i$, the neighbours of $v_i$ with larger indices form a clique of size at most $k-1$. Give every vertex an arbitrary list of at least $k$ colours. Colour in reverse order, always avoiding the colours already used by later neighbours. At most $k-1$ colours are forbidden, so the process gives a proper list-colouring.

This colouring is acyclic. If a two-coloured cycle existed, choose its vertex $v_i$ of smallest index. Its two cycle neighbours have larger indices and, because the cycle is properly two-coloured, have the same colour. But those two neighbours are adjacent by the ordering hypothesis, contradicting properness. This proves acyclic $k$-choosability for every graph with the stated order, with no assumption of a common palette.

In particular, start with a planar triangle and repeatedly insert a vertex inside a triangular face, joining it to all three boundary vertices. Reverse insertion order, followed by the three initial vertices, has later-neighbour cliques of size at most three. These stacked triangulations are acyclically four-choosable and hence satisfy the five-list target. Their subgraphs also inherit the result: first colour the same vertex set in the containing graph, and then delete edges. An induced subset of vertices inherits the restricted order as well. The proof explicitly uses the clique property, not merely a bound on the number of later neighbours.

A second family: cactus graphs with three-element lists.

A cactus has every block either a single edge or a simple cycle. Root its block structure and process blocks outward, so each new block meets the coloured portion in just one cutvertex $v_0$. For an edge block, colour its new endpoint differently from $v_0$, which requires only two available colours.

For a cycle $v_0v_1\cdots v_{m-1}v_0$, choose $c(v_1)$ different from $c(v_0)$, then choose $c(v_2)$ different from both. This is possible from three-element lists. If $m=3$, the block is already properly coloured with three distinct colours. If $m\ge4$, colour successive vertices through $v_{m-2}$ avoiding the preceding colour, and colour $v_{m-1}$ avoiding the two colours on $v_{m-2},v_0$. Every cycle block is proper and contains the three different colours on $v_0,v_1,v_2$. A simple cycle in a cactus lies entirely in one block, so no bichromatic cycle can cross the block decomposition. This proves acyclic three-choosability, including arbitrary overlaps among the lists. Disconnected components are processed separately.

A planar graph that really needs five colours.

The octahedral graph $K_{2,2,2}$ is planar: draw a four-cycle as an equator and put the two remaining nonadjacent vertices on opposite sides, each joined to all four equatorial vertices. In any proper colouring, colours used in different parts of the complete tripartite graph must be disjoint. If only four colours are available, at least two of its three two-vertex parts are monochromatic. Those two parts induce a two-coloured $K_{2,2}$, which is a cycle. Thus the graph is not acyclically four-colourable, and assigning the same four-element list everywhere disproves four-choosability.

Five colours suffice for this particular graph: use two distinct colours on each of two parts and a fifth colour on the remaining part. Each bichromatic induced subgraph then has at most three vertices, so cannot contain a cycle. This example proves necessity of the proposed constant; it supplies no counterexample to five-element lists.

Verification, obstruction and final status.

The elimination proof rules out a bichromatic cycle by inspecting its first vertex, so it covers cycles of every length without enumeration. The cactus extension preserves already assigned cutvertex colours, an essential condition for its inductive use with arbitrary lists. In contrast, merely greedy proper colouring of the cycle $C_4$ can produce the pattern $1,2,1,2$: a small later-neighbour count alone does not imply acyclicity. UNRESOLVED. A general planar graph need not have the clique elimination order or cactus blocks used above. The first remaining gap is an extension rule, valid for arbitrary five-lists, that prevents long two-coloured paths from closing into cycles when a vertex or configuration is inserted. Neither ordinary proper list-colouring nor ordinary acyclic colouring resolves that simultaneous requirement.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3244 (OPG-46940), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Acyclic list colouring of planar graphs.. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/acyclic_list_colouring_of_planar_graphs.

• R1 Luke Postle, Evelyne Smith-Roberge and Massimo Vicenzo, Acyclic List Colouring Locally Planar Graphs, 2024. Primary abstract checked 1 October 2026; distinguishes ordinary and list acyclic-colouring bounds. https://arxiv.org/abs/2412.09410.