Strong colorability

Strong colorability

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph and let $r\geq1$ be an integer. A partition $\mathcal P$ of $V$ into parts of size at most $r$ consists of nonempty pairwise disjoint subsets whose union is $V$. A strong $r$-colouring relative to $\mathcal P$ is a function $c:V\to\{1,\ldots,r\}$ that is proper on $G$ and injective on every part of $\mathcal P$.

The graph is strongly $r$-colourable if such a colouring exists for every partition into parts of size at most $r$. Different partitions may require different colourings. Equivalently, add all edges within each part to make it a clique; every graph produced this way must have chromatic number at most $r$.

The conjecture states that every finite simple graph of maximum degree $\Delta\geq1$ is strongly $2\Delta$-colourable. Explicitly, after any partition into parts of size at most $2\Delta$, one must colour the vertices with $2\Delta$ colours while distinguishing both adjacent vertices and vertices sharing a part.

The maximum degree is measured in $G$ before adding the partition edges. There is no restriction on how parts interact with edges, and no assumption that $|V|$ is divisible by $2\Delta$. The positive-degree condition avoids the undefined phrase strongly zero-colourable; edgeless graphs are trivially strongly $r$-colourable for every positive $r$ under this definition.

Short English statement

After any partition into groups of size at most twice the maximum degree, can a graph be coloured with that many colours so every group also receives distinct colours?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 1 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope.

Literature and a structural approach.

Axenovich and Martin [R1] prove the conjectured bound for graphs whose maximum degree is at least one sixth of their order. Their theorem is prior work; the argument below instead treats arbitrary disjoint unions of cliques, allowing partitions that cross between those cliques in any way. We keep the catalogue convention of parts of size at most the number of colours, rather than require equally sized parts.

Converting two partitions to an incidence multigraph.

Suppose $G$ is a disjoint union of cliques $C_1,\ldots,C_s$, and let $P_1,\ldots,P_t$ be the supplied partition. Construct a bipartite multigraph $H$ with one left vertex for each $C_i$ and one right vertex for each $P_j$. Each vertex $v$ of $G$ becomes an edge from its clique to its partition part. Distinct vertices in the same intersection give parallel edges, which must not be collapsed. A proper edge-colouring of $H$ gives distinct colours to vertices of $G$ within each $C_i$ and within each $P_j$. It is therefore exactly a strong colouring of $G$ for this partition. Both implications hold: the incidence construction does not introduce unwanted constraints between different intersections.

An elementary bipartite edge-colouring proof.

Let $d$ be the maximum degree of $H$. Add dummy vertices to balance the two bipartition sizes, then add edges, allowing parallel edges, until all degrees are $d$. This is possible because total degree deficiency on the two sides is equal; whenever a deficiency remains choose one deficient vertex on each side and join them. In the resulting regular multigraph, every left vertex set $X$ sends $d|X|$ edges to $N(X)$, whose vertices receive at most $d|N(X)|$ edges. Thus $|N(X)|\ge|X|$. Hall's theorem yields a perfect matching. Removing it leaves a regular bipartite graph of degree $d-1$, so induction partitions all edges into $d$ matchings. Give these matchings different colours and discard the dummy edges. This proves the required edge-colouring without assuming anything about simplicity of the incidence graph.

The resulting strong-colouring theorem.

If $G$ has maximum degree $\Delta$, its cliques have size at most $\Delta+1$. For every partition with parts of size at most $r$, the incidence graph has maximum degree at most $\max(\Delta+1,r)$. Consequently $G$ is strongly $r$-colourable for every $r\ge\Delta+1$. Taking $r=2\Delta$ proves the catalogue target for this entire class when $\Delta\ge1$. When $\Delta=1$ every component is a single vertex or edge, so this also proves the complete maximum-degree-one case. For an edgeless graph, assign colours independently and injectively within each part. A clique of order $\Delta+1$ explains why fewer than $\Delta+1$ colours cannot work universally even before partition edges are added.

Why two tempting extensions fail.

For a general graph, adding edges within parts of size $2\Delta$ gives maximum degree at most $3\Delta-1$. Greedy colouring therefore guarantees $3\Delta$ colours, not the required $2\Delta$. The incidence proof avoids that loss by using a genuine clique partition of the original graph; arbitrary neighbourhoods overlap and do not supply such a partition.

Another strategy chooses an independent transversal, gives it one colour, and repeats. An arbitrary first transversal can destroy extendibility. Take one edge $uv$ and isolated vertices $x,y$, with parts $\{u,x\}$ and $\{v,y\}$. The independent transversal $\{x,y\}$ is legal as a first colour class. The two remaining vertices are adjacent and cannot both receive the only remaining colour. A different transversal, such as $\{u,y\}$, does extend. The failure concerns greedy choice, not existence of a strong colouring.

Verification and final status.

The proof explicitly retains repeated intersections as parallel edges and handles unequal part sizes and isolated vertices. The root batch script checks the four-vertex failed-transversal example. UNRESOLVED. Disjoint unions of cliques satisfy a stronger bound, but extending the matching construction to graphs without a clique-component structure requires additional control of overlapping adjacency constraints.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3225 (OPG-171), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Strong colorability. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/strong_colorability.
• R1 Maria Axenovich and Ryan R. Martin, On the strong chromatic number of graphs, arXiv:1605.06574. Primary abstract checked 1 October 2026. https://arxiv.org/abs/1605.06574.