Degenerate colorings of planar graphs

Degenerate colorings of planar graphs

Definitions and mathematical statement

A finite graph $H$ is $d$-degenerate if every nonempty subgraph of $H$ has a vertex of degree at most $d$, with degree measured inside that subgraph. Equivalently, its vertices admit an ordering in which each vertex has at most $d$ neighbours later in the ordering. In particular, 0-degenerate graphs are edgeless and 1-degenerate graphs are forests.

Let $G$ be a finite simple planar graph. The conjecture asks for a colouring $c:V(G)\to\{1,2,3,4,5\}$ such that, for every $k\in\{1,2,3,4\}$ and every set $I\subseteq\{1,2,3,4,5\}$ of $k$ colour names, \[ G[c^{-1}(I)] \text{ is }(k-1)\text{-degenerate}. \] Unused colours and empty induced subgraphs are allowed. The $k=1$ condition ensures the colouring is proper. The $k=2$ condition then forbids all two-coloured cycles; the $k=3$ and $k=4$ conditions demand additional deletion orderings for the corresponding induced graphs. The ordering may depend on the chosen colour subset $I$.

The range stops at four. Requiring the same property for all five colours would force the whole graph to be 4-degenerate, which is false for planar graphs of minimum degree five. Thus the record's particular five-colour statement should not be strengthened by extending the displayed quantifier to $k=5$. The problem asks that all specified colour-subset conditions hold for one common colouring, not that each condition can be met by a different colouring.

Short English statement

Can every planar graph receive five colours so that any one, two, three, or four colour classes induce graphs of degeneracy at most zero, one, two, or three respectively?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 2 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. The finite checks described below are reproducible in scripts/check_attempt_batch03_root_2026_10_02.py.

The simultaneous requirement.

The same colouring must work for every subset of its palette. The $k=1$ condition is ordinary properness; the $k=2$ condition says that every two-colour induced subgraph is a forest. The latter is acyclic colouring, but the conditions for three and four colours add genuinely different requirements. The acyclic five-colour theorem reported in [S2] therefore cannot by itself discharge the statement. We prove the entire simultaneous requirement for a class containing all stacked planar triangulations, then give a small obstruction to this tempting implication from acyclic colouring.

An elimination-order lemma.

Suppose $v_1,\ldots,v_n$ is an ordering in which the later neighbours of each vertex form a clique of size at most three. Colour in reverse order, using a palette of four colours. At the time a vertex is coloured, its at most three already coloured neighbours forbid at most three colours, so a proper choice exists. Fix any $k$ colours, with $1\le k\le4$, and restrict the ordering to vertices carrying those colours. The remaining later neighbours of a vertex still form a clique. They have distinct colours, none equal to that vertex's own colour. Consequently at most $k-1$ remain. In every nonempty subgraph of this induced graph, its earliest vertex has degree at most $k-1$. This is precisely $(k-1)$-degeneracy. Viewing the four-colour palette as a subset of five colours causes no problem: a selected set containing the unused colour only weakens the bound. Thus one colouring satisfies all the required inequalities.

A planar class where the hypothesis holds.

Start with a plane $K_4$ and repeatedly insert a new vertex into a triangular face, joining it to the three corners. Order inserted vertices in reverse insertion order, followed by the original four vertices. The later neighbours of an inserted vertex are exactly its three older face corners, which form a clique. The last four vertices also have at most three later neighbours, forming a clique. The lemma therefore applies to every graph produced by this process. Moreover, any graph obtained by deleting edges or vertices from one of these triangulations inherits the colouring and the degree bounds. Edge deletion cannot increase the degree of a vertex in any induced colour subgraph. This extends the restricted result beyond maximal members of the class without assuming a special embedding for the subgraph itself.

Acyclic colouring does not supply the missing step.

Take a triangular prism with triangles $v_0v_1v_2$ and $w_0w_1w_2$ and matching edges $v_iw_i$. Give the top triangle colours $0,1,2$ in order and the bottom triangle colours $1,2,0$. This is proper. For each pair of colours the four vertices induce a path with three edges; direct inspection proves there is no two-colour cycle. Nevertheless the subgraph induced by all three used colours is the whole prism, whose minimum degree is three. It is not 2-degenerate, so this particular acyclic colouring fails the $k=3$ condition. Allowing two additional unused colours does not repair that failure. This is a counterexample to an implication between properties of a colouring, not a counterexample to the conjecture: the prism could admit a different acceptable colouring.

What an extension must control.

For an arbitrary planar graph, a low-degree deletion order need not make later neighbours a clique. They may repeat colours, and an entire selected three-colour subgraph may develop a nonempty 3-core even though every two-colour subgraph stays acyclic. A successful recolouring argument must simultaneously destroy these higher-colour cores; merely forbidding bichromatic cycles does not monitor them.

Verification and final status.

The root script checks the prism's three pair-induced paths and its 3-core, and checks the elimination lemma on deterministically generated stacked triangulations, including every palette subset. The general lemma is proved independently of those experiments. The stacked-triangulation and subgraph cases are established, while the full planar five-colour assertion remains unresolved here.

Sources

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