A Note on Graphs of Dichromatic Number 2

Raphael Steiner

arxiv: 1907.00351 · v1 · pith:I5GPIFYDnew · submitted 2019-06-30 · 🧮 math.CO

A Note on Graphs of Dichromatic Number 2

Raphael Steiner This is my paper

Pith reviewed 2026-05-25 12:48 UTC · model grok-4.3

classification 🧮 math.CO

keywords dichromatic numberplanar digraphsK5-minor-free graphsoriented graphsgraph colouringNeumann-Lara conjecture

0 comments

The pith

Neumann-Lara and Škrekovski conjecture on planar digraphs equals the claim that all oriented K5-minor-free graphs are 2-colourable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the conjecture every planar digraph is 2-colourable is logically equivalent to the statement that every oriented graph without a K5 minor is 2-colourable. This links a specific planar case directly to a wider class of graphs closed under taking minors. A reader cares because any proof or counterexample in the broader setting immediately settles the planar conjecture, and the reduction may simplify attacks on the original problem by allowing work within minor-closed families.

Core claim

The conjecture that every planar digraph is 2-colourable is equivalent to the more general statement that all oriented K5-minor-free graphs are 2-colourable.

What carries the argument

A direct reduction establishing equivalence between the planar case and the K5-minor-free case through the interaction of dichromatic number with the minor relation.

If this is right

If all oriented K5-minor-free graphs are 2-colourable then every planar digraph is 2-colourable.
If a planar digraph counterexample exists then an oriented K5-minor-free counterexample also exists.
The conjecture can be studied uniformly across all minor-closed classes that include the planar graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The equivalence may allow known results on colouring K5-minor-free graphs to be lifted to digraph orientations.
Similar reductions could apply to other forbidden-minor classes such as K4-minor-free graphs.
Testing colourability on small K5-minor-free graphs could give evidence for or against both statements at once.

Load-bearing premise

The dichromatic number interacts with the minor relation so that the planar case reduces directly to the K5-minor-free case.

What would settle it

An oriented K5-minor-free graph with dichromatic number greater than 2 whose reduction to a planar digraph fails to preserve the colourability bound, or a planar digraph counterexample that has no counterpart in the K5-minor-free class.

read the original abstract

Neumann-Lara and \v{S}krekovski conjectured that every planar digraph is $2$-colourable. We show that this conjecture is equivalent to the more general statement that all oriented $K_5$-minor-free graphs are $2$-colourable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This note shows the planar digraph 2-colorability conjecture is equivalent to the K5-minor-free version, with one direction immediate and the other requiring a reduction.

read the letter

The main thing here is that Steiner proves the Neumann-Lara–Škrekovski conjecture (every planar digraph is 2-colorable) is equivalent to the statement that every oriented K5-minor-free graph is 2-colorable. One direction is immediate since planar graphs have no K5 minor. The paper's contribution is handling the converse by showing that a counterexample in the larger class can be turned into a planar one. That equivalence is new as an explicit claim. The abstract and stress-test indicate no internal contradictions or unsupported steps, and the work stays within standard minor theory for digraphs. It does well by giving a minor-closed reformulation that might help people thinking about structural obstructions or possible counterexamples. The paper is short and focused, which fits the note format. Soft spots are limited and proportionate. The result does not resolve the conjecture or introduce new coloring techniques; it is a reformulation. If the reduction in the non-trivial direction turns out to be routine, that is fine for this kind of note but means the paper adds less than a full proof or counterexample would. No evidence of circularity or invented entities. This is for readers already working on dichromatic number, oriented coloring, or minor-closed graph classes. Someone tracking the planar conjecture might value the alternative statement for further attacks. It deserves a serious referee because the equivalence is cleanly stated and connects two versions of an open problem without overclaiming. I would send it out for review as a short communication rather than desk reject.

Referee Report

0 major / 0 minor

Summary. The manuscript proves that the Neumann-Lara–Škrekovski conjecture (every planar digraph has dichromatic number at most 2) is equivalent to the statement that every oriented K5-minor-free graph has dichromatic number at most 2.

Significance. The equivalence is a modest but useful clarification: one direction is immediate from the fact that planar graphs are K5-minor-free, while the converse direction supplies a reduction showing that any counterexample in the larger minor-closed class can be turned into a planar counterexample. This may assist future work on the conjecture by enlarging the search space for potential counterexamples or by connecting the problem to other minor-closed families.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept. The report correctly captures the main contribution: an equivalence between the Neumann-Lara–Škrekovski conjecture and the statement that every oriented K5-minor-free graph has dichromatic number at most 2.

Circularity Check

0 steps flagged

Equivalence between externally defined statements; no circular reduction

full rationale

The paper proves equivalence between the Neumann-Lara–Škrekovski conjecture (planar digraphs 2-colourable) and the statement that oriented K5-minor-free graphs are 2-colourable. One direction is immediate from the subclass relation (planar implies K5-minor-free). The converse requires a reduction mapping any counterexample in the larger class to one in the planar class. No equations, parameters, or self-citations are present that reduce a claimed result to its own inputs by construction. The derivation chain is self-contained and does not invoke any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests only on standard definitions and axioms of graph theory; no additional free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard axioms and definitions of directed graphs, dichromatic number, and graph minors
The equivalence is stated using these background notions.

pith-pipeline@v0.9.0 · 5547 in / 1097 out tokens · 63055 ms · 2026-05-25T12:48:37.798758+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that this conjecture is equivalent to the more general statement that all oriented K5-minor-free graphs are 2-colourable.
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 5 ([Wag37]). A simple graph is K5-minor-free if and only if it can be obtained from planar graphs and copies of V8 by means of repeated i-sums with i∈{0,1,2,3}.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.