For an undirected graph , let be the maximum dichromatic number of an orientation of . Its dichromatic number is the minimum number of vertex colours with no monochromatic directed cycle. Erdős and Neumann-Lara ask whether bounding bounds the ordinary chromatic number independently of the graph. The ordinary statement remains open in the sources checked. Erdős, pp. 16–18 · Problem 761 · Research issue
Mohar and Wu prove a fractional analogue, and Harutyunyan, Picasarri-Arrieta and Puig i Surroca prove a list analogue. Harutyunyan and Puig i Surroca prove a lower bound for Kneser graphs. Aboulker, Havet, Pirot and Schabanel give the bound . The first result below substitutes a bound in terms of maximum degree. The second gives an asymptotic result for finite shift graphs, for which Soukup had proved a directed-cycle colouring theorem in the uncountable setting. Exact-phrase, author, and citation searches turned up no resolution of the ordinary conjecture or a statement of either quantitative bound below. Fractional version · List version · Kneser graphs · Order bound · Soukup, Theorem 4.5
Maximum degree and orientations of dense subsets
Theorem. Every finite graph of maximum degree admits an orientation in which every acyclic induced subgraph has average degree less than . Consequently
More generally, fix , and let be the binary entropy function. There is an orientation such that for every connected induced subgraph of average degree at least , making the induced orientation acyclic requires deleting more than arcs. This is a local degree-dependent guarantee on every graph. A separate result of Lei, Wang and Wang obtains strong feedback-arc bounds for particular triangle-free graphs. Lei, Wang and Wang (2026)
Proof. For a connected graph of order , let be its spanning tree count. The number of acyclic orientations is by the spanning-tree expansion of the Tutte polynomial, since each tree has at most internally active edges. If an orientation can be made acyclic by deleting arcs, a linear order consistent with the remaining arcs gives an acyclic orientation differing on at most edges. The entropy bound on Hamming balls in therefore gives
in a uniformly random orientation. Stanley on acyclic orientations · Tutte polynomial, spanning-tree expansion
Take these bad events for connected induced subgraphs at or above the indicated average degree. Write and assign each event the local-lemma weight
For a fixed vertex , the sum of over connected -vertex sets containing is at most . Each counted tree is a rooted tree on distinct graph vertices, with root . Fix an order of the neighbours of each vertex to choose the order of children. There are at most shapes of ordered rooted trees, and at most ways to choose the images of children for each shape. Therefore the sum of over the events whose sets contain is at most .
Events on disjoint vertex sets are independent, and we can use every intersecting set as a possible dependency. For any the sum of weights of the other events that intersect it is at most . Each individual weight is at most , so and the product of over the dependency neighbourhood is at least . At the stated threshold the probability of the bad event for is at most , which is at most its weight times that product. The asymmetric Lovász local lemma avoids every bad event.
For , a disconnected acyclic induced subgraph at the threshold would have a connected component at the threshold. Thus every acyclic colour class and all its induced subgraphs have average degree below . Each class is therefore -degenerate and has a proper colouring with at most colours. Refining the acyclic colouring proves the bound for . In particular, the conjectured implication holds along every family with and .
Finite shift graphs
For fixed , let have the increasing -tuples of as vertices, and join to for every increasing -tuple. Set and write for the -fold iterated logarithm.
Theorem. For fixed ,
In fact there is an orientation requiring that many colours even to avoid monochromatic directed four-cycles, up to a term when and a term when .
Proof. Naturally orient in the increasing shift direction, including the increasing tournament when . Its arcs correspond to the vertices of . Each junction of this natural orientation gives a complete bipartite subgraph between the tuples that are incoming arcs and those that are outgoing arcs at . Choose an orientation of in which, at every junction, every two -sets on opposite sides induce a directed cycle, where . This is possible for sufficiently large by independent random orientations. For any fixed two sets the chance of acyclicity is at most because each acyclic orientation has a topological ordering. There are at most choices over all junctions and pairs of sets, and the product of these two bounds tends to zero. In an oriented complete bipartite subgraph a shortest directed cycle must have length four. A longer directed cycle has a chord between the first and fourth vertices that produces a shorter directed cycle in either direction.
Suppose a colouring with colours avoids monochromatic directed four-cycles. Assign to each junction the set of colours occurring at least times on its outgoing arcs. Every colour in occurs fewer than times on its incoming arcs. For each naturally directed edge of , let be the colour of its tuple in . Call the edge exceptional if . At most exceptional edges at a junction can be charged to rare outgoing colours, and at most to rare incoming colours. There are therefore at most exceptional edges. All other edges connect different palettes.
For , let be the sizes of the palette classes of the junctions. Every increasing pair in a class is exceptional, so
Thus . Apply this to a minimum colouring. The ordinary chromatic number is an upper bound for and is , giving .
For , choose uniformly a subset of alphabet symbols. Any exceptional edge is specified by symbols, all retained with probability at most . The expected number retained is at most for a minimum colouring, since . Thus there is a choice on which no exceptional edge survives. The palettes properly colour with at most colours, so .
For completeness, a proper colouring of gives disjoint incoming and outgoing colour sets at each junction. Taking the outgoing sets gives a proper colouring of with at most colours. Conversely, from a proper -colouring of assign distinct equal-cardinality subsets of as palettes for the colours, with . Colour each arc by an element in its tail palette and outside its head palette. At any junction the incoming and outgoing colours are disjoint, so this properly colours . Since one can choose , induction gives the stated asymptotic for , and in particular the upper bounds used above. The palette lower bound also gives for . A dicolouring must avoid monochromatic directed four-cycles, so the same lower bounds apply to .
Exact fractional chromatic numbers for Burling and twincut graphs
The two recursive constructions give arbitrarily large ordinary chromatic number. Their fractional chromatic numbers can also be calculated exactly. Their growth, combined with the theorem of Mohar and Wu, implies that neither sequence has bounded maximum dichromatic number. The unboundedness of fractional chromatic number for the class of Burling graphs is already known. The calculation here concerns the exact values for the original finite sequence and for the twincut sequence. Charbit and Sereni give the same recurrence as the twincut recurrence below for the distinct Zykov sequence, using a related lower-bound argument. Burling recursion as stated by Felsner et al., Section 1 · Twincut construction, Section 2 · Burling fractional unboundedness, reported by Steiner · Charbit–Sereni on Zykov products
Write a fractional colouring with palette of length as a set of measure one for each vertex , with disjoint sets on adjacent vertices. These sets can be finite unions of half-open intervals. To pass from a fractional colouring by weighted stable sets to this description, allocate an interval to each weighted stable set and trim any excess coverage at a vertex. For put . We will split a palette into two parts in any prescribed ratio by splitting every interval of the common refinement in that ratio. The split then divides every in that same ratio. Each part can be placed by a measure-preserving piecewise translation into any available palette region of sufficient measure.
Burling graphs. For the sequence of Felsner et al., and for . Indeed, put . The recursion starts at a single vertex with that singleton as the distinguished stable set. It uses a master copy of and, for each distinguished set in the master, another copy of . For each distinguished set in that other copy it adds a vertex adjacent to exactly . The new distinguished sets are and .
Inductively every fractional colouring of has a distinguished set with . For the step, take such an in the master and such an in its associated copy. If , we are done. Otherwise , and the palette of is disjoint from . Consequently . This establishes the induction and also gives , since the palette for avoids of measure at least .
For the upper bound, we maintain a colouring of of palette length with every distinguished set having union measure exactly . Take and for . For the step set and use a palette of length , placing the master colouring unchanged. For every master set , split the palette of its associated copy in the ratios and , placing the first part inside and the second outside. This fits since , so the two lengths are at most and , respectively. Thus every copy probe has and . The remaining palette outside has measure inside and outside . Give it all to . Now both new distinguished sets have palette union measure . This gives the asserted colouring of , of palette length .
Twincut graphs. For a rooted tree with levels, start at a single root. At level the children of every node at level induce a copy of the same graph . Add one vertex for each root-to-leaf branch, adjacent to all nodes of its branch. There are no edges except those of the sibling graphs and the branch adjacencies. Set and define
Then the fractional chromatic number of this graph is , with the first maximum omitted at height one.
For the lower bound, consider a branch prefix whose palettes have union of measure . Among the children in its next sibling graph , there is a vertex with . Otherwise all restricted palettes could be scaled by the reciprocal of their minimum measure to give a fractional colouring of of length strictly smaller than . The new palette union is therefore at least . This function is nondecreasing in because . Starting at the root, one can find a full branch of union measure at least . Its branch vertex needs a disjoint palette of measure one. Each is a subgraph, giving the other lower bound.
Conversely, use a palette of length . Give the root any palette of measure one. At each next sibling graph split an optimal palette of length to place length within the ancestor union and the rest outside. This fits since and . For every child the palette union along its branch prefix then has measure exactly . The complement of any full branch's union has measure at least one and supplies its branch vertex.
For the twincut graph , the tree has height , and for levels its sibling graphs are copies of . Thus satisfies and . In detail, , and if then . Squaring the recurrence gives , so .
Mohar and Wu give a maximum dichromatic number of order at least when . It follows that and . An Erdős–Neumann-Lara counterexample family would require a different construction. Mohar–Wu, Theorem 1.3
Graphs from the counterexample to the Erdős–Hajnal high-girth conjecture
Kohlmeyer and Kruer disproved the high-girth subgraph conjecture using underlying graphs of line digraphs of acyclic graphs. Nguyen and Walczak sharpened the construction to produce graphs of unbounded chromatic number all of whose -free subgraphs are 3-colourable. The construction also permits orientations requiring unboundedly many colours to avoid monochromatic directed four-cycles. Nguyen–Walczak, Theorems 1.3 and 2.1
Let be a finite simple digraph partitioned into nonempty sets , with all arcs going from a lower to a higher index. Suppose its maximum outdegree is at most . Write for the undirected graph of its arcs, adjacent when consecutive in a directed path. Give each vertex of weight . Suppose each independent set of the underlying graph of has total weight at most . For an integer , assume
If , then has an orientation in which every -colouring has a monochromatic directed four-cycle.
Proof. Orient the edges of independently at random. Consider a vertex of and any choice of colours and a linear order on its outgoing arcs. Call an incoming arc compatible if for some colour with at least outgoing arcs, its forward edges in the orientation of to those arcs form a suffix in their order. The signs for the edges from to an outgoing block of size are uniform on possibilities, of which are suffixes. Thus the chance that is compatible is at most .
Fix a layer and fix the choices of colours and orders at vertices in the higher layers. For , call bad if any arc out of is compatible at its head. The probability of this is at most . These events are independent across , because different incoming arcs at each junction use disjoint sets of edges of . For the probability of at least bad vertices is at most . Over all vertices in higher layers the number of choices of colours and orders is at most . The failure probability on each layer is thus at most , and these bounds sum to less than one because the are distinct positive integers. The final layer has no bad vertices. Fix an orientation for which every choice of colours and orders at higher layers leaves at least three quarters of each layer good.
Suppose there is a -colouring of the arc vertices with no monochromatic directed four-cycle. For every junction and every colour, its incoming and outgoing arcs of that colour induce an oriented complete bipartite graph. It is acyclic, since every cyclic orientation of a complete bipartite graph has a directed four-cycle. Choose the order on outgoing arcs of each colour from a topological order of that bipartite digraph, concatenating the orders over the colours. Any incoming arc whose colour appears on at least outgoing arcs is now compatible at that junction. Retain the good vertices of for these choices. Their combined weight is at least .
At a retained vertex let be the set of colours with at least outgoing arcs in the original . An arc with both endpoints retained and must have colour outside this common palette. If its colour belonged to the palette at , would be bad. There are at most arcs of colours outside the tail palette at any tail. Thus on vertices with any one palette the underlying graph has an acyclic orientation of maximum outdegree at most and is -colourable by reverse topological order. Over at most palettes this gives at most independent sets partitioning the retained vertices. Their total weight cannot reach under the given bound on . This contradiction proves the assertion.
The proof of Nguyen and Walczak's Theorem 2.1 supplies such a base for arbitrarily large , with and the stated weights. Each vertex has at most one arc to each higher layer, and the decay of the layer sizes in their construction can be taken as fast as the separation inequality above requires. Their Lemma 5.3 bounds the weight of independent sets with the same weights. Use the maximum-degree threshold there for their 3-colourability conclusion on -free subgraphs of . Our orientation gives the simultaneous lower bound
by taking for a sufficiently large constant . Meanwhile , since independent fair bits assigned to the base vertices select each arc with probability as a -to- arc, and these selected arcs always form an independent set of .
Iterated generalized Mycielski graphs
A generalized Mycielski step of height replaces a graph by layers of copies of its vertices and adds an apex adjacent to the last layer. An edge of is copied within layer zero and across each pair of successive layers. Write for the minimum palette size of a proper -fold colouring, where every vertex receives colours and neighbours receive disjoint colour sets. The base graph remains induced in layer zero. Pan–Zhu, Multiple Coloring of Cone Graphs
Blow-ups in later stages. Starting at any stage , after further generalized Mycielski steps of arbitrary positive heights, the result contains the induced blow-up of with independent copies of each vertex and complete bipartite links across the old edges. At one step, an independent set can be doubled by keeping all old vertices in layer zero and keeping the first-layer copies just for the vertices being doubled. These new copies have exactly the required adjacencies, since no two vertices being doubled are adjacent. Process the colour classes of an -fold colouring of one at a time, doubling all current copies of each vertex in the corresponding independent set. Each original vertex gets doubled exactly times.
When has no isolated vertices, is also the minimum number of steps needed by an embedding that uses only descendants of the original vertices, with each blow-up fibre projecting to its designated vertex of . To see this, index a descendant by its sequence of layer numbers. For original neighbours , at each coordinate every layer occupied by the fibre of must be adjacent to every layer occupied by the fibre of in the path of layers with a loop at zero. This looped path has neighbourhoods of size at most two, and any two distinct vertices have at most one common neighbour. Thus each fibre has at most two choices at each coordinate, and the fibres with two choices at a given coordinate form an independent set in . Each fibre of order needs at least such coordinates. The coordinates give an -fold colouring after discarding excess memberships.
Consequence for orientations. If , the blow-up with fibre size can be oriented so that every -colouring contains a monochromatic directed cycle of length four, provided for a sufficiently large constant . Mohar and Wu's Lemmas 3.1–3.2 give an orientation of each complete bipartite link in which every pair of subsets of size induces a directed cycle. A shortest directed cycle in an oriented complete bipartite graph has length four, since a chord to the vertex three steps ahead shortens any longer directed cycle. Choosing a most frequent colour per fibre would give a proper -colouring of if all such directed four-cycles were avoided. Mohar–Wu, Lemmas 3.1–3.2
Consequently every infinite iterated generalized Mycielski sequence with unbounded chromatic number has unbounded maximum dichromatic number, regardless of the positive heights chosen at its steps. Starting with , Stiebitz's theorem gives . Taking and so that , we have . The graph at step therefore has an orientation requiring colours even to avoid monochromatic directed four-cycles. Stiebitz's theorem, recalled by Almási–Gujgiczer–Simonyi
Long cones. Pan and Zhu show that a step of height at least raises by at most one. Any step raises it by at most , by keeping the original -fold colouring in every layer and using new colours at the apex. If is the number of heights below among the first steps from , then
In particular, if the height at step satisfies , then for the preceding choice we have . Indeed, all have heights at least once is sufficiently large. After total steps we can force colours to avoid monochromatic directed four-cycles. Thus the lower bound along these sequences is . Pan–Zhu
For example, heights also allow bounded fractional chromatic number. Tardif's formula says the fractional increment at height is , with measured before the step. The first step is , with . All subsequent increments are bounded by , a summable sequence. Hence the orientation bound for these long cones applies in a regime where the fractional chromatic number stays bounded. Tardif, Fractional Chromatic Numbers of Cones over Graphs