{"id":"4bd2de4a-9fce-4eb8-b5e2-82d211278054","arxiv_id":"1908.02883","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every orientation of a connected cubic graph has an oriented 8-coloring, and every orientation of a cubic graph has a 2-dipath 7-coloring.","lead":"This paper proves that every orientation of a connected cubic graph can be colored with eight colors under a strict directed-edge coloring rule, improving the previous best bound of nine. It also proves every orientation of a cubic graph admits a seven-color 2-dipath coloring, and shows the older Sopena conjecture is now equivalent to a sharp dichotomy.","discovery_kind":"extension","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7802,"tokens_out":34657,"duration_ms":413231,"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":[{"comment":"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.","section":"Section 2, Lemma 5"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"Lemma 4"},{"comment":"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.","section":"Lemma 5"},{"comment":"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.","section":"Lemma 11"},{"comment":"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.","section":"Lemma 11"}],"recommendation":"major_revision","confidential_remarks":"The paper is a short note with a potentially interesting result, but the gap in Lemma 5 is load-bearing: without a correct extension argument, Theorem 6 is not proven. The 2-dipath part of the paper seems sound, and the counting in Lemma 11 is intricate but convincing. I recommend major revision; the author should supply a full justification of the extension step or restructure the proof of Theorem 6, and should also clarify the small omissions listed in the minor comments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real result, not a remark. Duffy proves that every orientation of a connected cubic graph has oriented chromatic number at most 8, improving the previous 9, and that every orientation of a cubic graph has 2-dipath chromatic number at most 7, matching the known lower bound. If both hold, Sopena's conjecture is pinned to a neat dichotomy: either it is false, or the oriented and 2-dipath chromatic numbers coincide on cubic graphs. Worth knowing.\n\nWhat is new: the 8-bound removes the source-sink condition from the earlier 8-result in [3], and the 2-dipath bound is exact. The proofs are mostly straightforward reductions to a published theorem of Duffy-MacGillivray-Sopena that properly subcubic graphs without a degree-3 source adjacent to a degree-3 sink map to QR7. There is no circularity; the cited theorem is separate and published.\n\nThe good: the paper is clearly written, the lemmas hang together, and the key insight in Lemma 5—delete a vertex, add an arc, then extend the QR7 homomorphism—is plausible. Lemma 11's counting argument, while dense, bounds eC correctly and gets the contradiction. The result for disconnected cubic graphs is honestly flagged in the discussion, and the connection to 2-dipath colourings is a nice closing observation.\n\nWhere I would push: Lemma 5 is the load-bearing step and it is the most compressed. The extension of φ to the deleted vertex x uses arc-transitivity and vertex-transitivity of QR7, but the verification that the recoloured u and the new x do not create bad adjacencies is sketched. That is the place I would want a referee to check line by line. Lemma 3 also has a slightly wandering walk argument, but it is not wrong. Lemma 9 uses Brooks' theorem with a non-complete condition; the appeal to Proposition 3.3 of [3] is fine, but the wording around the oriented clique could be tightened.\n\nOverall, the central claims hold up under my reading. This deserves a serious referee and likely a minor-revision accept. The paper is aimed at graph homomorphism and oriented colouring audiences, and it moves a long-standing problem.","headline":"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.","tokens_in":8313,"tokens_out":2124,"would_cite":true,"duration_ms":20853,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every orientation of a connected cubic graph admits an oriented 8-colouring.","keywords":["oriented chromatic number","2-dipath colouring","cubic graphs","Paley tournament","graph homomorphism","oriented colouring","chromatic dichotomy"],"falsifier":"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.","tokens_in":7646,"feed_emoji":"🎨","tokens_out":7693,"duration_ms":63660,"temperature":0.7,"pith_summary":"This note proves two colouring bounds for orientations of cubic graphs. First, every orientation of a connected cubic graph has an oriented 8-colouring, lowering the previous upper bound of 9. Second, every orientation of a cubic graph, connected or not, admits a 2-dipath 7-colouring, and this bound is tight. Because a 7-vertex lower bound was already known for connected cubic orientations, the two results force a dichotomy: either the 1997 conjecture that 7 colours always suffice for such graphs is false, or the oriented and 2-dipath chromatic numbers coincide on this family at 7.","feed_headline":"Eight colours suffice for any orientation of a connected cubic graph","feed_subtitle":"Either the 7-colour conjecture for cubic orientations is false, or oriented and 2-dipath chromatic numbers coincide.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Theorem 1, the QR7 homomorphism theorem for connected properly subcubic oriented graphs, and the source/sink corollary; the 8-colour proof builds auxiliary graphs specifically to invoke it.","marker":"[3]"},{"why":"Gives the transitivity and directed-cycle extension properties of QR7 that allow colourings to be adjusted and removed vertices to be reinserted.","marker":"[6]"},{"why":"Provides the lower bound ω(F_3^2) = 7, which makes the new 2-dipath 7-colouring tight.","marker":"[2]"},{"why":"States the 1997 conjecture that the oriented chromatic number of connected cubic orientations is 7, the conjecture directly addressed by the dichotomy.","marker":"[8]"}],"fun_headline_variants":["Cubic orientations: 8 colours always enough","Oriented cubic graphs: 8-colour bound","8 colours for any connected cubic orientation","New upper bound: 8 colours for cubic orientations","Cubic orientations: 8-colourable, 2-dipath 7-colourable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cubic orientations: 8 colours always enough","Oriented cubic graphs: 8-colour bound","8 colours for any connected cubic orientation","New upper bound: 8 colours for cubic orientations","Cubic orientations: 8-colourable, 2-dipath 7-colourable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001052,"raw_usage":{"total_tokens":4333,"prompt_tokens":772,"completion_tokens":3561,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":388,"completion_tokens_details":{"reasoning_tokens":3481}},"tokens_in":388,"tokens_out":3561,"duration_ms":25981,"temperature":1.0,"reasoning_tokens":3481,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:36:05.103836+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Oriented colourings of graphs with maximum degree three and four","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 1, the QR7 homomorphism theorem for connected properly subcubic oriented graphs, and the source/sink corollary; the 8-colour proof builds auxiliary graphs specifically to invoke it."},{"cited_title":"Homomorphism bounds for oriented planar graphs","cited_arxiv_id":null,"evidence_quote":"Gives the transitivity and directed-cycle extension properties of QR7 that allow colourings to be adjusted and removed vertices to be reinserted."},{"cited_title":"A study on oriented relative clique number","cited_arxiv_id":null,"evidence_quote":"Provides the lower bound ω(F_3^2) = 7, which makes the new 2-dipath 7-colouring tight."},{"cited_title":"The chromatic number of oriented graphs","cited_arxiv_id":null,"evidence_quote":"States the 1997 conjecture that the oriented chromatic number of connected cubic orientations is 7, the conjecture directly addressed by the dichotomy."}],"review_version":1}