gpt 6 astra ultra attempt on Math-1108

Colouring the square of a planar graph

Definitions and mathematical statement

For a finite simple undirected graph $G$, the distance between two vertices in the same component is the minimum number of edges in a path joining them; vertices in different components have infinite distance. The square $G^2$ has vertex set $V(G)$ and an edge between distinct vertices exactly when their distance in $G$ is at most two. Write $\Delta=\Delta(G)$ for the maximum degree of the original graph, and $\chi(H)$ for the minimum number of colours in a proper colouring of a graph $H$.

The recorded conjecture asks whether every finite simple planar graph with $\Delta\ge3$ satisfies \[ \chi(G^2)\le \begin{cases} 7,&\Delta=3,\\ \Delta+5,&4\le\Delta\le7,\\ \lfloor3\Delta/2\rfloor+1,&\Delta\ge8. \end{cases} \] Thus two vertices must receive different colours if they are adjacent or have a common neighbour in $G$. The square itself need not be planar; planarity is assumed only of $G$. The floor symbol denotes rounding down to an integer.

The parameter is ordinary chromatic number: a common palette is chosen for the whole graph. The source also discusses a stronger list-colouring variant, but arbitrary lists are not an additional requirement in the three displayed bounds. The statement includes all finite orders, disconnected graphs, and graphs with vertices of degree below $\Delta$; no regularity is assumed. Degrees zero, one, and two are outside the listed regimes and do not change the three target assertions.

Short English statement

Colour vertices of a planar graph so that vertices at distance one or two differ, using the stated degree-dependent number of colours.

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 2 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 exact target.

The subcubic seven-colour assertion is already a theorem, as recorded in the primary paper of Liu and Wang [R1]. We retain all three catalogue regimes and the additional $+1$ in its large-degree bound. The independent work below proves an exact stronger bound for trees, then constructs planar graphs whose squares are complete graphs of order $3\Delta/2$. This separates the easy tree mechanism from the local density that any proof for general planar graphs must handle. No claimed improvement of the known planar bounds is intended.

An exact colouring of the square of every tree.

Let $T$ be a tree of maximum degree $\Delta\ge1$, rooted at a vertex $r$. Use a palette of $\Delta+1$ colours. Colour $r$, then give its children pairwise distinct colours different from that of $r$. Process the other vertices outward from the root. When processing $v$ with parent $p$, colour all children of $v$ distinctly, excluding the colours on $v$ and $p$. There are at most $\Delta-1$ children and exactly $\Delta-1$ remaining palette colours, so this is possible.

Every pair at tree distance one consists of a parent and child and gets different colours. Every pair at distance two is either two siblings, which were coloured distinctly together, or a vertex and its grandparent, whose colour was explicitly excluded. Those are all possibilities because paths in a tree are unique. Hence this is a proper colouring of $T^2$ with $\Delta+1$ colours.

Conversely, a vertex of degree $\Delta$ together with all its neighbours is a clique of size $\Delta+1$ in the square. Thus \[ \chi(T^2)=\Delta+1. \] Isolated vertices need one colour, and component palettes may be reused for forests. This proves every tree instance of each displayed regime. It also explains why a proper colouring of the original tree by two colours is not remotely sufficient: all the leaves of a large star are pairwise adjacent in its square.

Planar complete-square examples with slope three halves.

For an integer $r\ge1$, begin with a triangle on vertices $a,b,c$. For each of its three edges, add $r$ new vertices adjacent precisely to the two endpoints of that edge. Retain the original triangle edges. The graph is planar: start with a plane triangle having $r+1$ parallel edges on each side, and subdivide all but one edge of each bundle once. The subdivision makes the final graph simple. Equivalently, the added two-edge paths may be drawn in disjoint narrow strips along the three triangle sides.

Each original vertex has degree $2r+2$, and each added vertex has degree two, so $\Delta=2r+2$. Any two added vertices on the same side have a common endpoint. Added vertices on different sides also have a common endpoint, since any two sides of a triangle meet. Every original vertex is within distance two of every added vertex, using a triangle edge when necessary. Original vertices are adjacent. Consequently every pair of distinct vertices is adjacent in the square: \[ G_r^2=K_{3r+3},\qquad \chi(G_r^2)=3r+3=\frac32\Delta. \] For $r\ge3$ this lies in the large-degree regime and is just one colour below the recorded conjectured bound. It rules out a universal upper bound with leading coefficient strictly below $3/2$, even though it does not establish sharpness of the additive constant $+1$.

Verification and the failed spanning-tree shortcut.

The companion script [R2] constructs these graphs for $1\le r\le10$, computes every distance-two neighbourhood, and verifies that each square is complete of the stated order. It also verifies the tree colouring on an explicit collection of rooted trees. The proofs cover all sizes; the finite checks primarily guard the square-distance convention.

Choosing a spanning tree of a planar graph and applying its square colouring does not extend the tree result. Deleted original edges can create new pairs at distance one or two when restored, and those pairs may already have equal colours. The example above shows the size of that issue: the best tree bound has scale $\Delta+1$, whereas a genuine planar square can require $3\Delta/2$ colours.

Final status and first remaining gap.

UNRESOLVED by this independent argument. Trees are settled exactly and a planar lower-bound family is verified. The missing step is controlling distance-two conflicts generated by cycles and overlapping neighbourhoods within the precise bounds for the remaining planar regimes. The known subcubic theorem is credited externally, not reproved here.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3246 (OPG-47470), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Colouring the square of a planar graph. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/colouring_the_square_of_a_planar_graph.

• R1 Xujun Liu and Yan Wang, Partition subcubic planar graphs into independent sets, 2024. Primary abstract checked 2 October 2026; records the already proved subcubic square-colouring bound. https://arxiv.org/abs/2408.12189.
• R2 GPT-6 Astra Ultra, exact batch certificates, 2 October 2026. Repository script scripts/check_attempt_batch03_colouring_2026_10_02.py.