Coloring the union of degenerate graphs

Coloring the union of degenerate graphs

Definitions and mathematical statement

A finite simple graph $H$ is $d$-degenerate if every nonempty subgraph of $H$ has a vertex of degree at most $d$. Equivalently, its vertices can be ordered so that each has at most $d$ neighbours later in the order. A $1$-degenerate graph is precisely a forest, that is, a graph with no cycle.

Let $G_1=(V,E_1)$ be $1$-degenerate and $G_2=(V,E_2)$ be $2$-degenerate, on a common finite vertex set $V$. If originally their vertex sets differ, enlarge each by isolated vertices first. Their union is the simple graph $G=(V,E_1\cup E_2)$; overlapping edges are counted only once.

The conjecture asserts that every such union has a proper vertex colouring with at most five colours: \[ \chi(G_1\cup G_2)\leq5. \] Equivalently, there is $c:V\to\{1,2,3,4,5\}$ with $c(u)\neq c(v)$ whenever $uv$ belongs to either edge set. The decomposition is part of the hypothesis, but its two degeneracy orderings need not agree.

The elementary product construction uses six colours: greedily two-colour the forest, three-colour the $2$-degenerate graph, and label each vertex by its pair of colours. Every edge has different labels in at least one coordinate. The problem asks whether this universal bound can always be reduced to five, while still simultaneously respecting all edges of both graphs.

Short English statement

Is the union of a forest and a 2-degenerate graph always properly colourable with five colours?

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.

Literature and approach.

The Garden entry [S2] attributes the question to Tarsi, gives the six-colour product bound and notes that five would be sharp. We test whether an elimination proof can reach five colours. The positive result below requires a bounded maximum degree in one of the two input graphs; degeneracy alone does not impose that maximum-degree condition. Overlapping edges are counted only once, so all degree sums used below are upper bounds.

The general union has a six-colour elimination order.

A forest on $k\ge1$ vertices has at most $k-1$ edges. A 2-degenerate simple graph on $k\ge2$ vertices has at most $2k-3$ edges: remove a vertex of degree at most two repeatedly, with at most one edge at the two-vertex stage. Summing the removal counts gives $2(k-2)+1$. The same bounds apply to every induced subgraph of the respective input graph.

For any set $X$ of $k\ge2$ vertices, therefore, \[ |E((G_1\cup G_2)[X])|\le(k-1)+(2k-3)=3k-4<3k. \] The average degree is less than six, so some vertex has degree at most five. Singleton induced subgraphs present no issue. Thus the union is 5-degenerate. Remove vertices of degree at most five and then colour them in reverse removal order: each newly coloured vertex sees at most five already coloured neighbours, so six colours suffice. This yields the same numerical baseline as product colouring by a different, directly checkable mechanism.

A sharp five-colour subclass.

Suppose additionally that $G_1$ has maximum degree at most two; since it is a forest, it is a disjoint union of paths and isolated vertices. For any nonempty $X$, 2-degeneracy of $G_2[X]$ supplies a vertex $v$ with $d_{G_2[X]}(v)\le2$. At that very same vertex $d_{G_1[X]}(v)\le2$, hence \[ d_{(G_1\cup G_2)[X]}(v)\le4. \] The union is consequently 4-degenerate and five-colourable by reverse elimination. This holds for arbitrary interactions between the paths and $G_2$, not merely for edge-disjoint inputs.

A second sufficient condition is $\Delta(G_2)\le3$, with no maximum-degree restriction on the forest. Every nonempty induced forest has a vertex of degree at most one; at that vertex the union degree is at most $1+3=4$. Again every induced union has a removable degree-four vertex, proving the target.

A tight example inside the first subclass.

On vertices $0,1,2,3,4$, let $G_1$ have path edges $01,12,23,34$ and let \[ E(G_2)=\{02,03,04,13,14,24\}. \] These edge sets partition $E(K_5)$. In $G_2$, removing vertices in the order $1,3,0,2,4$ encounters degrees $2,1,2,1,0$, respectively. Thus $G_2$ is 2-degenerate, while $G_1$ is a path forest. Their union needs five colours because it is $K_5$. So even the restricted theorem cannot have four in place of five.

The script scripts/check_attempt_batch02_graphs_2026_10_01.py verifies this edge partition and the exact removal degrees. In particular, the example also disproves the tempting claim that the union is always $(1+2)$-degenerate: $K_5$ is not 3-degenerate.

The first obstruction beyond these subclasses.

If a union were not five-colourable, a vertex-minimal non-five-colourable induced subgraph would have minimum degree at least five. Otherwise deleting a degree-at-most-four vertex, colouring the remainder and reinserting it would succeed. In such a subgraph every forest leaf or isolated vertex must have degree at least four in $G_2$, and every vertex of $G_2$-degree at most two must have forest degree at least three. Both types of low-degree vertex exist separately, but they need not be the same vertex. Adding the two minimum-degree guarantees as if they applied at one common vertex is the missing, invalid step in a universal four-degeneracy proof.

Final status.

The six-colour elimination bound and two sharp five-colour subclasses are proved. No argument here forces a degree-four vertex, or otherwise a five-colouring, in every unrestricted union. The general catalogue statement is UNRESOLVED by this attempt.

Sources

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