Coloring digraphs with $\Delta-b$ colors

Ken-ichi Kawarabayashi; Lucas Picasarri-Arrieta

REVIEW 1 major objections 6 minor 34 references

Coloring digraphs with $\Delta-b$ colors

T0 review · 1 major / 6 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Δ−b colors suffice for digraphs with small bicliques

desk verdict Extends Reed's coloring theorem to digraphs with a clever vertex-identification technique; proof is intricate but largely holds together. read the letter →

arxiv 2607.06928 v1 pith:2JUVVTDF submitted 2026-07-08 math.CO cs.DM

Ken-ichi Kawarabayashi , Lucas Picasarri-Arrieta This is my paper · ORCID

classification math.COcs.DM

keywords dichromaticnumberdigraphcoloringbicliquedensedecompositionvertexidentificationLovászLocalLemmaReed'stheoremBorodin-Kostochkaconjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that for every fixed integer b, every digraph D whose maximum geometric-mean degree Δ̃(D) is sufficiently large (relative to b) and whose largest biclique has size at most Δ̃(D) − 2b can have its vertices partitioned into at most Δ̃(D) − b acyclic sets. This is the directed analogue of a classical theorem of Reed for undirected graphs, where the same statement holds with maximum degree replacing Δ̃ and clique number replacing biclique number. The bound is tight: for every b and Δ ≥ 3b, there exists a digraph with Δ̃ = Δ, dichromatic number exactly Δ − b + 1, and largest biclique exactly Δ − 2b + 1. The result supports the authors' broader conjecture that every digraph satisfies χ⃗(D) ≤ ⌈½(Δ̃(D) + 1 + ω↔(D))⌉, a directed version of Reed's conjecture for graphs.

What carries the argument

Vertex identifications inside tight dense sets create repeated colors in savior neighborhoods, compensating for the lack of external neighbors and allowing a random partial coloring to extend. The Lovász Local Lemma applies because each bad event depends on only polynomially many others, guaranteed by D⋆ preserving distances up to a factor of three.

What would settle it

An explicit digraph with Δ̃(D) ≥ Δ_b, biclique number at most Δ̃(D) − 2b, and dichromatic number exceeding Δ̃(D) − b, for some fixed b and arbitrarily large Δ̃.

Watch

Extended reading notes

Core claim

The proof combines a dense decomposition — partitioning the digraph into sparse vertices and near-biclique dense sets — with a probabilistic coloring argument on an auxiliary digraph D⋆. The central innovation is vertex identification: inside tight dense sets (those whose bicliques have size Δ̃ − O(b)), carefully chosen pairs of exceptional vertices are merged into single vertices in D⋆. When D⋆ is randomly colored and then partially uncolored wherever a color appears in both the in- and out-neighborhood of a vertex, these identifications force repeated colors in the neighborhoods of savior vertices — vertices that lie in the biclique and have many external neighbors. The repeated colors补偿 (

Load-bearing premise

The entire proof rests on a Dense Decomposition Lemma cited from a 2025 preprint by overlapping authors, which guarantees that every large-degree digraph partitions into sparse vertices and near-biclique dense sets; if this structural decomposition fails to provide the guarantees claimed, the subsequent analysis of saviors, rescuers, and the probabilistic coloring argument collapses.

Editorial extensions

If this is right

The directed analogue of Reed's Δ−b coloring theorem holds, confirming that the same degree-versus-clique-number tradeoff governs both directed and undirected coloring.
The biclique threshold Δ̃ − 2b is best possible for digraphs — unlike the undirected case where the threshold may be improvable — because directed cycles inside biclique blow-ups create obstructions with no undirected analogue.
The result provides evidence for Conjecture 5, the directed version of Reed's conjecture χ ≤ ⌈½(Δ + 1 + ω)⌉, which would unify this theorem with the directed Brooks theorem.
The vertex identification technique may transfer to other coloring problems where dense substructures limit the flexibility of probabilistic arguments, particularly in settings where the degree parameter is a geometric or arithmetic mean of in- and out-degrees.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If Conjecture 5 is eventually proven, the threshold Δ_b in this theorem would become unnecessary — the statement would hold for all Δ̃, not just sufficiently large ones, paralleling how Conjecture 4 strengthens Corollary 3 in the undirected case.
The vertex identification technique could potentially apply to oriented graph coloring (Problems 8 and 9 in the paper), where the maximum out-degree Δ⁺ replaces Δ̃, though the authors note this extension remains open.
The tightness construction — blowing up b vertices of a biclique into directed triangles — suggests that the interplay between directed cycles and bicliques is fundamentally more constrained than the undirected interplay between odd cycles and cliques, which may have consequences for the structure of dichromatic-critical digraphs.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper extends Reed's 1998 result (Corollary 3: graphs with large Δ and small clique number have χ ≤ Δ−b) to digraphs, replacing chromatic number with dichromatic number, maximum degree with the geometric-mean parameter Δ̃, and clique number with biclique number. The main theorem (Theorem 7) states that for every fixed b, every digraph with Δ̃ large enough and biclique number ≤ Δ̃−2b has dichromatic number ≤ Δ̃−b. The bound is tight, which is a nice touch — the extremal construction is simple and convincing. This is a genuine result, not a routine translation. The key methodological novelty is the vertex identification step in Section 4.4: in tight dense sets, where saviors don't have enough external neighbors to guarantee easy coloring, the authors identify pairs of exceptional vertices to force repeated colors into savior neighborhoods. This is a clean idea and the main reason the proof goes through. The structural claims (Claims 21, 23, 27) showing that dense sets contain many saviors are well-argued, and the probabilistic analysis via Lovász Local Lemma is carried out in reasonable detail. The soft spots are real but not fatal. First, the required threshold Δ_b ≥ 2^{Ω(b²)} is far from the linear bound in the undirected case. The authors acknowledge this and say sharper arguments could reduce it, which is honest but means the quantitative result is weak. Second, the proof depends on the Dense Decomposition Lemma (Lemma 13) from a 2025 preprint [16] by overlapping authors. This isn't circular in the logical sense — the lemma is stated as a black box with clear conditions — but its correctness hasn't been independently verified yet. Third, regarding the stress-test concern about distance preservation in D⋆: the argument in Section 4.5.3 is indeed stated informally. The claim is that identifying two vertices with a common neighbor means distance-6 in D maps to distance-at-most-2 in D⋆, giving a factor-3 blowup. This is correct as far as it goes — identified pairs do share neighbors by Claim 26 — but the step is not formalized as carefully as the rest of the proof. If the factor degraded to 4, the LLL dependency bound would need exponent 17 instead of 13 in inequality (∆9), which would likely still hold but hasn't been checked. This is the one place where a careful referee should ask for a more explicit argument. Overall, the central argument holds up. The paper is for specialists in digraph coloring who are comfortable with the probabilistic method and dense decomposition machinery. It deserves a serious referee who can verify the LLL application and the structural decomposition in detail.

Referee Report

1 major / 6 minor

Summary. The paper proves a directed analogue of Reed's classical result (Corollary 3 in the manuscript) on coloring graphs with $k$ colors when the clique number is bounded. Specifically, Theorem 7 (restated as Theorem 17) shows that for every fixed integer $b$, there exists a threshold $Delta_b$ such that every digraph $D$ with $tilde{Delta}(D) geq Delta_b$ and biclique number $overleftrightarrow{omega}(D) leq tilde{Delta}(D) - 2b$ satisfies $vec{chi}(D) leq tilde{Delta}(D) - b$, where $tilde{Delta}(D) = max_v sqrt{d^+(v) cdot d^-(v)}$. The result is shown to be tight via a blowing-up construction. The proof combines a Dense Decomposition Lemma (from [16]), structural analysis of dense sets via the notions of saviors and rescuers, vertex identifications in tight dense sets to create an auxiliary digraph $D^star$, and a probabilistic coloring argument via the Lovász Local Lemma.

Significance. This is a substantial contribution to the directed coloring program. It extends a classical theorem of Reed to the directed setting, supports Conjecture 5 (a directed analogue of Reed's conjecture), and the tightness result confirms that the $-2b$ threshold is best possible in the directed case (unlike the undirected case where it is only known to be tight up to $o(b)$ terms). The vertex identification technique introduced for tight dense sets is a novel methodological contribution that may find further applications. The result is also stated for a general class of degree parameters beyond $tilde{Delta}$, adding to its scope. The lower bound construction is explicit and verifiable.

major comments (1)

§4.5.3 (Lovász Local Lemma application): The distance-preservation argument for $D^star$ is stated informally. The text asserts that 'whenever two vertices are identified, they have at least one neighbor in common' (from Claim 26), so distance-$2$ in $D^star$ maps to distance-at-most-$6$ in $D$, yielding a dependency radius of $12$ and hence $(2Delta)^{12}$ dependent events. While I believe this factor of $3$ is correct (each hop in $D^star$ involving an identified vertex corresponds to a path of length $leq 3$ in $D$ via the common neighbor), the argument should be stated as a formal lemma or claim with a proof. This is load-bearing: the exponent $13$ in inequality ($Delta_9$) depends on this factor being exactly $3$. I note that even if the factor were slightly larger (say $4$), the LLL would still apply for sufficiently large $Delta$ since $exp(log^2(Delta))$ grows faster than any $n$

minor comments (6)

The tightness construction is described in two places with slightly different parametrizations. The abstract states $tilde{Delta}(D) = Delta$ with $Delta geq 3b$, while §1 (page 4) states $tilde{Delta}(D) geq Delta$ with the construction being 'a biclique on $Delta+1$ vertices.' These are consistent (the body uses a different $Delta$ parameter than the abstract), but a brief sentence reconciling the two would help the reader.
Claim 30: The bound per identified pair is $d^+(v_j) + d^-(v_j) - 2|N^{pm}(u_j) cap N^{pm}(v_j)| leq 2(Delta+b+1) - 2(Delta-29b+2) = 60b - 2$, but the text writes $60b$. This is a valid upper bound (since $60b-2 < 60b$) but the slight looseness should be acknowledged or the exact bound used.
The list of inequalities ($Delta_1$)–($Delta_9$) is long and the reader must trust that they are all eventually satisfied. A brief remark after the list confirming that each inequality holds for $Delta geq 2^{C b^2}$ for some absolute constant $C$ (which is evident from inspection) would improve readability.
Figure 1 (page 14): The caption references $R_i$, $U^star_i$, $K^star_i$, and $Y_i$, but the figure itself is not rendered in the text version. If this figure is essential, ensure it is clearly produced in the final version.
The notation $overleftrightarrow{omega}$ for the biclique number is introduced in §1 but the symbol does not render in all contexts; consider defining it more prominently or using $omega_{leftrightarrow}$ as an alternative.
Page 4, line on Problem 8: 'It is a consequence of the Directed Brooks Theorem [19] that every oriented graph $D$ with $Delta^+(D) geq 2$ satisfies $vec{chi}(D) leq Delta^+(D)$.' This should perhaps note that the bound $vec{chi}(D) leq Delta^+(D)$ for oriented graphs follows more directly from the greedy coloring argument in §3.2, since oriented graphs have no digons.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the proof is self-contained with minor self-citations to independently stated lemmas

full rationale

The paper proves Theorem 7 (restated as Theorem 17) via a self-contained argument combining the Dense Decomposition Lemma (Lemma 13, cited from [16]), structural analysis of dense sets (Claims 18-27), a random coloring process on an auxiliary digraph D* (Section 4.4), and a probabilistic analysis using the Lovász Local Lemma (Section 4.5). The derivation chain is internally consistent: each claim follows from previous claims and the stated inequalities (Delta 1)-(Delta 9). The two self-citations—to Lemma 13 from [16] and Theorem 6 from [22]—are to independently stated results with their own proofs, not to results that are defined in terms of the present paper's conclusion. Lemma 13 provides a structural decomposition with explicit conditions (a)-(c) that do not reference the dichromatic number bound being proved. Theorem 6 is a weaker coloring bound that motivates but does not logically entail Theorem 7. The tightness construction (blowing up b vertices of a biclique into directed triangles) is an explicit example, not a fitted parameter repackaged as a prediction. No step in the proof reduces to its inputs by construction, and no 'prediction' is statistically forced by a fit. The distance-preservation argument in Section 4.5.3 is informal but is a correctness concern, not a circularity concern. The proof is a genuine mathematical derivation, not a renaming or self-referential construction.

Assumptions & free parameters 3 free parameters · 5 assumptions · 3 invented entities

The proof relies on standard mathematical tools (LLL, Talagrand, Azuma) and one domain-specific structural result (Dense Decomposition Lemma from a concurrent preprint). The parameter ε_b = 1/(24b) is hand-tuned. The threshold Δ_b is defined by explicit inequalities rather than fitted to data. The invented entities (saviors, rescuers, D*) are well-motivated and their properties are proved within the paper.

free parameters (3)

b = fixed positive integer (input parameter)
The integer b is the main parameter of the theorem, controlling how far below Δ the coloring bound sits. It is an input, not fitted.
ε_b = 1/(24b)
The sparsity parameter for the Dense Decomposition Lemma, chosen as 1/(24b) in Section 4. This is a hand-tuned constant selected to make the inequalities (∆1–∆9) work.
Δ_b = smallest integer satisfying (∆1)–(∆9)
The degree threshold, defined as the smallest integer satisfying nine explicit inequalities. The authors note it is at least 2^{Ω(b²)}.

assumptions (5)

domain assumption Dense Decomposition Lemma (Lemma 13, from [16])
States that every digraph with large maximum degree admits a partition into sparse vertices and dense sets behaving like near-bicliques. Invoked in Section 4.1 (Claim 19). This is the structural foundation of the entire proof.
standard math Lovász Local Lemma (Lemma 14)
Standard probabilistic tool used in Section 4.5.3 to conclude that the random partial coloring is extendable with positive probability.
standard math Talagrand's concentration inequality (Lemma 15)
Used in Subclaim 31.2 to show concentration of the random variable Z_s counting repeated colors in sparse neighborhoods.
standard math Azuma's inequality (Lemma 16)
Used in Subclaim 32.4 to show concentration of the random variable T counting rescuers in dense sets.
ad hoc to paper Minimality of counterexample D
The proof argues by contradiction assuming D is a smallest counterexample. This is used throughout to extend partial colorings (Claims 18, 20, 21, 23, 27).

invented entities (3)

Saviors (loose and tight) independent evidence
purpose: Vertices inside dense set bicliques with many neighbors outside that are 'independent' of the biclique, making them easy to color in the random process.
Defined structurally in Sections 4.2–4.3; their existence is proved (Claims 23, 27) and their role in the coloring extension is demonstrated (Claim 28).
Rescuers (loose and tight) independent evidence
purpose: Saviors that are actually easy to color in the realized random partial coloring, serving as the bridge between structure and probability.
Defined in Section 4.4; their existence with high probability is proved in Claims 31 and 32.
Auxiliary digraph D* independent evidence
purpose: Obtained from D by identifying matched vertex pairs in tight dense sets, ensuring they receive the same color and creating repeated colors in savior neighborhoods.
Constructed in Section 4.4; its degree and sparsity properties are verified in Claims 29 and 30.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coloring digraphs with $\Delta-b$ colors." pith.science (2026). https://pith.science/paper/2JUVVTDF

@misc{pith2026260706928,
  author       = {Pith},
  title        = {Pith review of: Coloring digraphs with $\Delta-b$ colors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2JUVVTDF}},
  note         = {Machine review of arXiv:2607.06928}
}

abstract

The dichromatic number of a digraph is the minimum number of colors needed to partition its vertex set into acyclic subdigraphs. A biclique is a set of vertices inducing all possible pairs of opposite arcs. For a digraph $D$, define $\Delta(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We prove that, for every fixed integer $b\in\mathbb{N}$, every digraph $D$ with $\Delta(D) = \Delta$ being sufficiently large with respect to $b$ either contains a biclique whose size exceeds $\Delta-2b$ or has dichromatic number at most $\Delta-b$. This extends a classical result of Reed to the directed setting and supports a conjecture of the present authors. Furthermore, the theorem is tight, as for all integers $b$ and $\Delta\geq 3b$ there exists a digraph $D$ with $\Delta(D)= \Delta$, dichromatic number $\Delta-b+1$, and whose largest biclique has size $\Delta-2b+1$.

Figures

Figures reproduced from arXiv: 2607.06928 by the authors.

**Figure 1.** An illustration of Ri , U ⋆ i , K⋆ i , and Yi . The matching M⋆ i is highlighted in orange. A solid digon between two sets illustrates the presence of all possible such digons. The dashed digon illustrates that vertices in U ⋆ i are linked with digons to almost all vertices in K⋆ i . The dotted lines illustrate that |Xi \ N ±(r)| ⩾ 13b for every r ∈ Ri . used on L ′ j is also used on Ki \ yj . Therefore, since d +(… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

[16]

$(\Delta-1)$-dicolouring of digraphs

A. Harutyunyan, K. Kawarabayashi, L. Picasarri-Arrieta, and G. Puig i Surroca.(∆−1)- dicolouring of digraphs.Preprint arXiv:2507.10266, 2025

work page Pith review arXiv 2025
[1]

Aboulker and G

P. Aboulker and G. Aubian. Four proofs of the Directed Brooks’ Theorem.Discrete Mathematics, page 113193, 2022

work page 2022
[2]

Digraph Colouring and Arc-Connectivity

P. Aboulker, G. Aubian, and P. Charbit. Digraph colouring and arc-connectivity.Preprint arXiv:2304.04690, 2023

work page Pith review arXiv 2023
[3]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. John Wiley & Sons, 2016

work page 2016
[4]

K. Azuma. Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

work page 1967
[5]

Bang-Jensen and G

J. Bang-Jensen and G. Z. Gutin.Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2nd edition, 2009

work page 2009
[6]

Bang-Jensen, T

J. Bang-Jensen, T. Schweser, and M. Stiebitz. Digraphs and variable degeneracy.SIAM Journal on Discrete Mathematics, 36(1):578–595, 2022

work page 2022
[7]

Bonamy, T

M. Bonamy, T. Perrett, and L. Postle. Colouring graphs with sparse neighbourhoods: Bounds and applications.Journal of Combinatorial Theory, Series B, 155:278–317, 2022

work page 2022

Show all 34 references

[8]

O. V. Borodin and A. V. Kostochka. On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density.Journal of Combinatorial Theory, Series B, 23(2-3):247–250, 1977

1977
[9]

R. L. Brooks. On colouring the nodes of a network.Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194–197, 1941. COLORING DIGRAPHS WITH ˜∆−bCOLORS 29

1941
[10]

Delcourt and L

M. Delcourt and L. Postle. On the list coloring version of Reed’s conjecture.Electronic Notes in Discrete Mathematics, 61:343–349, 2017. The European Conference on Combi- natorics, Graph Theory and Applications (EUROCOMB’17)

2017
[11]

P. Erdős. Problems and results in number theory and graph theory. InProceedings of the ninth Manitoba Conference on Numerical Mathematics and Computing, pages 3–21, 1979

1979
[12]

Erdős and L

P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions.Infinite and Finite Sets, 10(2):609–627, 1975

1975
[13]

Farzad, M

B. Farzad, M. Molloy, and B. Reed. (∆−k)-critical graphs.Journal of Combinatorial Theory, Series B, 93(2):173–185, 2005

2005
[14]

Golowich

N. Golowich. The m-degenerate chromatic number of a digraph.Discrete Mathematics, 339(6):1734–1743, 2016

2016
[15]

Gonçalves, L

D. Gonçalves, L. Picasarri-Arrieta, and A. Reinald. Brooks-type colourings of digraphs in linear time.Preprint arXiv:2405.05222, 2024

2024 arXiv
[17]

Harutyunyan and B

A. Harutyunyan and B. Mohar. Strengthened Brooks'theorem for digraphs of girth at least three.The Electronic Journal of Combinatorics, 18(P195), 2011

2011
[18]

Hurley, R

E. Hurley, R. de Joannis de Verclos, and R. J. Kang. An improved procedure for colouring graphs of bounded local density.Advances in Combinatorics, 2022

2022
[19]

Jacob and H

H. Jacob and H. Meyniel. Extension of Turán’s and Brooks’ theorems and new notions of stability and coloring in digraphs.Combinatorial Mathematics, 75:365–370, 1983

1983
[20]

Johansson

A. Johansson. Asymptotic choice number for triangle free graphs. Technical report, DIMACS Technical Report 91-95, 1996

1996
[21]

AnanalogueofReed’sconjecturefordigraphs

K.KawarabayashiandL.Picasarri-Arrieta. AnanalogueofReed’sconjecturefordigraphs. Preprint arXiv:2407.05827, 2024

2024 arXiv
[22]

Kawarabayashi and L

K. Kawarabayashi and L. Picasarri-Arrieta. An analogue of Reed’s conjecture for di- graphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3310–3324. SIAM, 2025

2025
[23]

A. D. King and B. A. Reed. A short proof thatχcan be boundedεaway from∆ + 1 towardω.Journal of Graph Theory, 81(1):30–34, 2015

2015
[24]

B. Mohar. Eigenvalues and colorings of digraphs.Linear Algebra and its Applications, 432(9):2273–2277, 2010

2010
[25]

Molloy and B

M. Molloy and B. Reed. A bound on the total chromatic number.Combinatorica, 18(2):241–280, 1998

1998
[26]

Molloy and B

M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence.Combinatorics, probability and computing, 7(3):295–305, 1998

1998
[27]

Molloy and B

M. Molloy and B. Reed.Graph colouring and the probabilistic method. Algorithms and Combinatorics. Springer, Berlin, Germany, Nov. 2001

2001
[28]

Molloy and B

M. Molloy and B. Reed. Colouring graphs when the number of colours is almost the maximum degree.Journal of Combinatorial Theory, Series B, 109:134–195, 2014

2014
[29]

Picasarri-Arrieta

L. Picasarri-Arrieta. Strengthening the Directed Brooks’ Theorem for oriented graphs and consequences on digraph redicolouring.Journal of Graph Theory, 106(1):5–22, 2024

2024
[30]

Picasarri-Arrieta and M

L. Picasarri-Arrieta and M. Stiebitz. Generalized dp-colorings of digraphs.Preprint arXiv:2509.17471, 2025

2025
[31]

Reed.ω,∆, andχ.Journal of Graph Theory, 27(4):177–212, 1998

B. Reed.ω,∆, andχ.Journal of Graph Theory, 27(4):177–212, 1998

1998
[32]

B. Reed. A strengthening of Brooks’ theorem.Journal of Combinatorial Theory, Series B, 76(2):136–149, 1999

1999
[33]

R. Steiner. A note on coloring digraphs of large girth.Discrete Applied Mathematics, 287:62–64, 2020

2020
[34]

Talagrand

M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, 81:73–205, 1995. 30 K. KA W ARABAYASHI AND L. PICASARRI-ARRIETA National Institute of Informatics, The University ...

1995

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.

[1] [16]

$(\Delta-1)$-dicolouring of digraphs

A. Harutyunyan, K. Kawarabayashi, L. Picasarri-Arrieta, and G. Puig i Surroca.(∆−1)- dicolouring of digraphs.Preprint arXiv:2507.10266, 2025

work page Pith review arXiv 2025

[2] [1]

Aboulker and G

P. Aboulker and G. Aubian. Four proofs of the Directed Brooks’ Theorem.Discrete Mathematics, page 113193, 2022

work page 2022

[3] [2]

Digraph Colouring and Arc-Connectivity

P. Aboulker, G. Aubian, and P. Charbit. Digraph colouring and arc-connectivity.Preprint arXiv:2304.04690, 2023

work page Pith review arXiv 2023

[4] [3]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. John Wiley & Sons, 2016

work page 2016

[5] [4]

K. Azuma. Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

work page 1967

[6] [5]

Bang-Jensen and G

J. Bang-Jensen and G. Z. Gutin.Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2nd edition, 2009

work page 2009

[7] [6]

Bang-Jensen, T

J. Bang-Jensen, T. Schweser, and M. Stiebitz. Digraphs and variable degeneracy.SIAM Journal on Discrete Mathematics, 36(1):578–595, 2022

work page 2022

[8] [7]

Bonamy, T

M. Bonamy, T. Perrett, and L. Postle. Colouring graphs with sparse neighbourhoods: Bounds and applications.Journal of Combinatorial Theory, Series B, 155:278–317, 2022

work page 2022