REVIEW 1 major objections 5 minor 10 references
A Note on Colourings of Connected Oriented Cubic Graphs
T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Every orientation of a connected cubic graph admits an oriented 8-colouring.
desk verdict Duffy's note genuinely lowers the connected cubic oriented chromatic bound to 8 and pins the 2-dipath number at 7; the proofs rest on a published QR7 theorem and warrant a careful refereeing pass, with closest attention to the compressed extension step in Lemma 5. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proofs revolve around the 7-vertex Paley tournament QR7, whose vertices are the residues modulo 7 with an arc from u to v when v − u is a nonzero quadratic residue. QR7 is vertex-transitive and arc-transitive, and it has a two-way extension property for precoloured directed paths. The paper relies on a prior theorem stating that every connected properly subcubic oriented graph with no degree-3 source adjacent to a degree-3 sink maps homomorphically to QR7. To prove the 8-colour bound, the author reduces a cubic graph to such subcubic graphs by deleting an arc or a vertex, applies the QR7 theorem, and then uses QR7's extension properties to reinsert the removed vertex with a fresh eighth colour. The 2-dipath argument instead builds the auxiliary undirected graph G2 whose chromatic number equals the 2-dipath chromatic number, shows G2 has average degree 7, and then uses Brooks' theorem and a careful counting argument to rule out needing more than 7 colours.
What would settle it
A finite computer search over all orientations of connected cubic graphs with at least 20 vertices, checking whether each admits a homomorphism to every 8-vertex oriented graph, would find a counterexample to the 8-colour theorem if one exists; likewise, any cubic orientation whose auxiliary square graph G2 has chromatic number 8 would refute the 2-dipath 7-colouring claim.
Extended reading notes
Core claim
The central result is Theorem 6: if G is an orientation of a connected cubic graph, then its oriented chromatic number satisfies χo(G) ≤ 8. The paper also proves Theorem 12: every orientation of a cubic graph has 2-dipath chromatic number at most 7, which together with the known lower bound gives χ2d(F3) = 7 exactly. These two statements imply that the oriented chromatic number of the family of connected cubic orientations lies in {7, 8}, so either the long-standing 1997 conjecture that this number is 7 is false, or it is true and equals the 2-dipath chromatic number of the family.
Load-bearing premise
The proofs depend on a previously proved guarantee that every connected properly subcubic oriented graph without a degree-3 source adjacent to a degree-3 sink maps into the 7-vertex tournament QR7; if that guarantee fails for one of the auxiliary graphs built in the arguments, the 8-colour bound no longer follows.
Editorial extensions
If this is right
- The oriented chromatic number of the family of connected cubic orientations is now known to be either 7 or 8; no such orientation can require 9 colours.
- If the 1997 conjecture is true, then every connected cubic orientation with 2-dipath chromatic number 7 also has oriented chromatic number 7, making the two parameters equal on this family.
- If the conjecture is false, the family's true oriented chromatic number is exactly 8, witnessed by some connected cubic orientation.
- The 2-dipath chromatic number of all orientations of cubic graphs is exactly 7, matching the known lower bound.
- A new route to settling the conjecture is to study the oriented chromatic number of subgraphs of the universal 2-dipath target H7, since the dichotomy reduces the problem to whether such subgraphs can force oriented chromatic number 8.
Reading between the lines
- A concrete computational follow-up would be to search all orientations of connected cubic graphs with at least 20 vertices for one with oriented chromatic number 8; such a graph would have to avoid every reduction used in Lemmas 4 and 5, giving a sharp structural profile of any counterexample.
- The equality phenomenon may extend beyond cubic graphs: just as 2-regular orientations already satisfy χo = χ2d = 5, other bounded-degree families might show the same coincidence, and the paper's dichotomy suggests testing this directly.
- If no 8-chromatic cubic orientation exists, then the auxiliary graph G2 and the QR7 extension properties together point toward a potential proof strategy: show that every connected cubic orientation maps into QR7 after suitable local modifications, rather than relying on a separate eighth colour.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies oriented chromatic numbers and 2-dipath chromatic numbers of orientations of cubic graphs. It claims two main results: every connected oriented cubic graph admits an oriented 8-colouring (Theorem 6), improving the earlier bound of 9, and every orientation of a cubic graph admits a 2-dipath 7-colouring (Theorem 12). The arguments combine a published theorem of Duffy, MacGillivray, and Sopena (Theorem 1 here), which states that connected properly subcubic oriented graphs with no degree-3 source adjacent to a degree-3 sink map homomorphically to the Paley tournament QR7, with structural lemmas specific to cubic graphs. The final section draws a dichotomy: either Sopena's conjecture is false, or the oriented chromatic number and the 2-dipath chromatic number coincide at 7 on connected cubic graphs.
Significance. If the proofs are correct, Theorem 6 narrows the oriented chromatic number of connected cubic graphs to the set {7,8}, and Theorem 12 settles the 2-dipath chromatic number of cubic graphs at 7. These are concrete, falsifiable bounds and the connection drawn between oriented colouring and 2-dipath colouring gives a new perspective on Sopena's conjecture. A strength of the paper is that it contains no fitted parameters or ad hoc constructions: it relies on published structural results and on explicit properties of QR7. The counting argument in Lemma 11 is intricate and largely convincing. However, the proof of the first main result currently rests on an unjustified extension step in Lemma 5, so the 8-colouring theorem is not established as written.
major comments (1)
- [Section 2, Lemma 5] The extension of the homomorphism φ to the deleted vertex x is not justified and is false as stated. The proof invokes part (2) of Lemma 2, but that lemma only asserts that for a given arc yz of QR7 there exist vertices forming directed triangles with that arc. The extension requires a colour a satisfying three simultaneous conditions: φ(z)→a, a→φ(u), and a→φ(y). This need not hold. In QR7 with vertices 0,...,6 and arcs i→j when j−i is a nonzero quadratic residue modulo 7, take (φ(z),φ(u),φ(y)) = (1,3,2). Then φ(y)→φ(z) holds, and φ(u)→0 is compatible with φ(v)=0, but no vertex a satisfies 1→a, a→3, and a→2. The proof neither rules out this configuration nor shows that the homomorphism produced by Theorem 1 can be chosen to avoid it. Since this extension is exactly the step that produces the 8-colouring, Theorem 6 does not follow from the argument presented.
minor comments (5)
- [Throughout] There are numerous typographical errors (for example 'Saskatc hewan', 'a dmits', 'fur ther', 'im ply', 'cu bic'); the manuscript should be carefully proofread before resubmission.
- [Lemma 4] The reduction to two possible orientations of the triangle should be stated more carefully: the transitive orientation in which the third vertex w is the source is not one of the two listed cases. It can be handled by reversing all arcs of G and using the fact that QR7 is isomorphic to its converse, but this step is omitted.
- [Lemma 5] The claims that G′ is properly subcubic and connected deserve a few words of justification; they follow respectively from the degree changes at x, u, y, and z and from the fact that xu is not a cut arc, but the current text states them without argument.
- [Lemma 11] The sentence 'every proper subgraph of G admits a homomorphism to QR7' should be justified explicitly: a vertex of degree 3 in a proper subgraph retains all three incident edges, so its status as a degree-3 source or sink is inherited from G; with this observation the claim is correct, but the proof should say so.
- [Lemma 11] The term 'induced 2-dipath' is used without definition and can be ambiguous; the counting arguments appear to be correct for directed 2-paths regardless of chords, so a brief clarification would improve readability.
Circularity Check
No significant circularity: the new bounds are derived from independent prior theorems and a fixed target QR7, not from the claims being proved.
full rationale
The paper's central results, χo(G) ≤ 8 for connected cubic orientations and χ2d(G) ≤ 7 for cubic orientations, are proved by constructing or extending homomorphisms to QR7. The load-bearing Theorem 1 is quoted from [3], a separately published paper co-authored by the present author, but it is an independent prior theorem: it asserts that every connected properly subcubic oriented graph with no degree-3 source adjacent to a degree-3 sink maps to QR7. The present paper applies this theorem to auxiliary graphs such as G−uv, G′, and GC; it does not define those graphs in terms of the conclusion, and the conclusion is not a restatement of Theorem 1. The 2-dipath results use standard facts (Brooks' Theorem, Lemma 2 from [6], Proposition 3.3 from [3], and ω(F_3^2)=7 from [2]) as external inputs rather than as renamings of the claim. No parameter is fitted to data, no quantity is defined by reference to the target bound, and the dichotomy in Section 4 is a logical consequence of the two proved inequalities, not an input to them. The self-citation is therefore a normal reliance on previously published work and does not make the derivation circular.
Assumptions & free parameters
assumptions (6)
- domain assumption Theorem 1 of [3]: connected properly subcubic oriented graphs with no degree-3 source adjacent to degree-3 sink map homomorphically to QR7.
- domain assumption Lemma 2 of [6]: QR7 is vertex transitive and arc transitive, and for every arc yz there are two vertices completing directed cycles xyz.
- standard math Brooks' theorem: a connected graph with maximum degree Δ has chromatic number at most Δ unless it is complete or an odd cycle.
- domain assumption Proposition 3.3 of [3]: no orientation of a cubic graph is an oriented clique on 8 vertices.
- domain assumption Corollary 4.9 of [3]: connected cubic oriented graphs with a source or sink have oriented chromatic number at most 8.
- domain assumption ω(F_3^2) = 7 from [2]: the family of graphs G2 for cubic orientations has clique number 7.
Cite this review
Pith. "Pith review of A Note on Colourings of Connected Oriented Cubic Graphs." pith.science (2026). https://pith.science/paper/WWGJK6EC
@misc{pith2026190802883,
author = {Pith},
title = {Pith review of: A Note on Colourings of Connected Oriented Cubic Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/WWGJK6EC}},
note = {Machine review of arXiv:1908.02883}
}
read the original abstract
In this note we show every orientation of a connected cubic graph admits an oriented 8-colouring. This lowers the best-known upper bound for the chromatic number of the family of orientations of connected cubic graphs. We further show that every such oriented graph admits a 2-dipath 7-colouring. These results imply that either the chromatic number for the family of oriented connected cubic graphs equals the 2-dipath chromatic number or the long-standing conjecture of Sopena [Journal of Graph Theory 25:191-205 1997] regarding the chromatic number of orientations of connected cubic graphs is false.
Reference graph
Works this paper leans on
-
[3]
Oriented colourings of graphs with maximum degree three and four
Christopher Duffy, Gary MacGillivray, and ´Eric Sopena. Oriented colourings of graphs with maximum degree three and four. Discrete Mathematics, 342(4):959–974, 2019
work page 2019
- [1]
-
[2]
A study on oriented relative clique number
Sandip Das, Swathy Prabhu, and Sagnik Sen. A study on oriented relative clique number. Discrete Mathematics, 341(7):2049–2057, 2018
work page 2018
-
[4]
Oriented coloring of graphs with low maximum degree
Janusz Dybizba´ nskia, Pascal Ochem, Alexandre Pinlou, and And rzej Szepietowskia. Oriented coloring of graphs with low maximum degree. Discrete Mathematics, 343(5), 2020. 8
work page 2020
-
[5]
A Theory of 2 −dipath Colourings
Gary MacGillivray and Kailyn Sherk. A Theory of 2 −dipath Colourings. Australasian Journal of Com- binatorics, 60(1):11–26, 2014
work page 2014
-
[6]
Homomorphism bounds for oriented planar graphs
TH Marshall. Homomorphism bounds for oriented planar graphs. Journal of Graph Theory , 55(3):175– 190, 2007
work page 2007
-
[7]
Arc-coloration et sommet-coloration orient´ ees
Alexandre Pinlou. Arc-coloration et sommet-coloration orient´ ees. PhD thesis, Bordeaux 1, 2006
work page 2006
-
[8]
The chromatic number of oriented graphs
´Eric Sopena. The chromatic number of oriented graphs. Journal of Graph Theory , 25:191–205, 1997
work page 1997
Show all 10 references
-
[9]
Homomorphisms and colourings of oriented graphs: An updated survey
´Eric Sopena. Homomorphisms and colourings of oriented graphs: An updated survey. Discrete Mathe- matics, 339(7):1993–2005, 2016
1993
-
[10]
2-dipath and Proper 2 −dipath Colouring
Kailyn Young. 2-dipath and Proper 2 −dipath Colouring. Master’s thesis, University of Victoria, 2009. 9
2009
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.