Erdős–Neumann-Lara conjecture

For an undirected graph GG, let δ(G)\delta(G) be the maximum dichromatic number of an orientation of GG. Its dichromatic number is the minimum number of vertex colours with no monochromatic directed cycle. Erdős and Neumann-Lara ask whether bounding δ(G)\delta(G) bounds the ordinary chromatic number χ(G)\chi(G) 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 χ(G)≤2δ(G)(1+⌊log2|V(G)|⌋)\chi(G)\le 2\delta(G)(1+\lfloor\log_2 |V(G)|\rfloor). 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 GG of maximum degree Δ≥1\Delta\ge1 admits an orientation in which every acyclic induced subgraph has average degree less than 2log2Δ+102\log_2\Delta+10. Consequently

δ(G)≥χ(G)⌈2log2Δ+10⌉.\delta(G)\ge \frac{\chi(G)}{\lceil 2\log_2\Delta+10\rceil}.

More generally, fix 0≤η<1/20\le\eta\lt1/2, and let h2h_2 be the binary entropy function. There is an orientation such that for every connected induced subgraph HH of average degree at least (2log2Δ+10)/(1−h2(η))(2\log_2\Delta+10)/(1-h_2(\eta)), making the induced orientation acyclic requires deleting more than η|E(H)|\eta|E(H)| 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 HH of order ss, let τ(H)\tau(H) be its spanning tree count. The number of acyclic orientations is TH(2,0)≤2s−1τ(H)T_H(2,0)\le2^{s-1}\tau(H) by the spanning-tree expansion of the Tutte polynomial, since each tree has at most s−1s-1 internally active edges. If an orientation can be made acyclic by deleting jj arcs, a linear order consistent with the remaining arcs gives an acyclic orientation differing on at most jj edges. The entropy bound on Hamming balls in {0,1}|E(H)|\{0,1\}^{|E(H)|} therefore gives

Pr(H requires deletion of at most η|E(H)| arcs)≤2s−1τ(H)2−(1−h2(η))|E(H)|\Pr(H\text{ requires deletion of at most }\eta |E(H)|\text{ arcs}) \le 2^{s-1}\tau(H)\,2^{-(1-h_2(\eta))|E(H)|}

in a uniformly random orientation. Stanley on acyclic orientations · Tutte polynomial, spanning-tree expansion

Take these bad events for connected induced subgraphs HH at or above the indicated average degree. Write X=V(H)X=V(H) and assign each event the local-lemma weight

xX=τ(H)(8Δ)−|X|.x_X=\tau(H)(8\Delta)^{-|X|}.

For a fixed vertex vv, the sum of τ(G[X])\tau(G[X]) over connected ss-vertex sets XX containing vv is at most (4Δ)s−1(4\Delta)^{s-1}. Each counted tree is a rooted tree on distinct graph vertices, with root vv. Fix an order of the neighbours of each vertex to choose the order of children. There are at most 4s−14^{s-1} shapes of ordered rooted trees, and at most Δs−1\Delta^{s-1} ways to choose the images of children for each shape. Therefore the sum of xXx_X over the events whose sets contain vv is at most 1/(4Δ)1/(4\Delta).

Events on disjoint vertex sets are independent, and we can use every intersecting set as a possible dependency. For any XX the sum of weights of the other events that intersect it is at most |X|/(4Δ)|X|/(4\Delta). Each individual weight is at most 1/41/4, so log(1−xY)≥−2xY\log(1-x_Y)\ge-2x_Y and the product of 1−xY1-x_Y over the dependency neighbourhood is at least exp(−|X|/(2Δ))≥2−|X|\exp(-|X|/(2\Delta))\ge2^{-|X|}. At the stated threshold the probability of the bad event for XX is at most τ(G[X])(16Δ)−|X|\tau(G[X])(16\Delta)^{-|X|}, which is at most its weight times that product. The asymmetric Lovász local lemma avoids every bad event.

For η=0\eta=0, 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 2log2Δ+102\log_2\Delta+10. Each class is therefore ⌈2log2Δ+10⌉−1\lceil 2\log_2\Delta+10\rceil-1-degenerate and has a proper colouring with at most ⌈2log2Δ+10⌉\lceil 2\log_2\Delta+10\rceil colours. Refining the acyclic colouring proves the bound for δ(G)\delta(G). In particular, the conjectured implication holds along every family with χ(G)→∞\chi(G)\to\infty and logΔ=o(χ(G))\log\Delta=o(\chi(G)).

Finite shift graphs

For fixed r≥2r\ge2, let Sr(n)S_r(n) have the increasing rr-tuples of [n][n] as vertices, and join (x1,…,xr)(x_1,\ldots,x_r) to (x2,…,xr+1)(x_2,\ldots,x_{r+1}) for every increasing (r+1)(r+1)-tuple. Set S1(n)=KnS_1(n)=K_n and write log2(j)\log_2^{(j)} for the jj-fold iterated logarithm.

Theorem. For fixed r≥2r\ge2,

δ(Sr(n))∼χ(Sr(n))∼log2(r−1)n.\delta(S_r(n))\sim\chi(S_r(n))\sim\log_2^{(r-1)}n.

In fact there is an orientation requiring that many colours even to avoid monochromatic directed four-cycles, up to a term O(loglogn)O(\log\log n) when r=2r=2 and a term Or(1)O_r(1) when r≥3r\ge3.

Proof. Naturally orient Sr−1(n)S_{r-1}(n) in the increasing shift direction, including the increasing tournament when r=2r=2. Its arcs correspond to the vertices of Sr(n)S_r(n). Each junction uu of this natural orientation gives a complete bipartite subgraph between the tuples that are incoming arcs and those that are outgoing arcs at uu. Choose an orientation of Sr(n)S_r(n) in which, at every junction, every two tt-sets on opposite sides induce a directed cycle, where t=⌈4log2n⌉t=\lceil4\log_2 n\rceil. This is possible for sufficiently large nn by independent random orientations. For any fixed two sets the chance of acyclicity is at most (2t)!2−t2(2t)!2^{-t^2} because each acyclic orientation has a topological ordering. There are at most nr−1+2tn^{r-1+2t} 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 qq colours avoids monochromatic directed four-cycles. Assign to each junction uu the set P(u)P(u) of colours occurring at least tt times on its outgoing arcs. Every colour in P(u)P(u) occurs fewer than tt times on its incoming arcs. For each naturally directed edge u→vu\to v of Sr−1(n)S_{r-1}(n), let cc be the colour of its tuple in Sr(n)S_r(n). Call the edge exceptional if c∉P(u)\P(v)c\notin P(u)\setminus P(v). At most q(t−1)q(t-1) exceptional edges at a junction can be charged to rare outgoing colours, and at most q(t−1)q(t-1) to rare incoming colours. There are therefore at most 2q(t−1)(nr−1)2q(t-1)\binom{n}{r-1} exceptional edges. All other edges connect different palettes.

For r=2r=2, let mim_i be the sizes of the palette classes of the nn junctions. Every increasing pair in a class is exceptional, so

n2/2q−n2≤∑i(mi2)≤2q(t−1)n.\frac{n^2/2^q-n}{2}\le\sum_i\binom{m_i}{2}\le 2q(t-1)n .

Thus 2q≥n/(1+4q(t−1))2^q\ge n/(1+4q(t-1)). Apply this to a minimum colouring. The ordinary chromatic number is an upper bound for qq and is O(logn)O(\log n), giving q≥log2n−O(loglogn)q\ge\log_2 n-O(\log\log n).

For r≥3r\ge3, choose uniformly a subset of m=⌊n1/(2r)⌋m=\lfloor n^{1/(2r)}\rfloor alphabet symbols. Any exceptional edge is specified by rr symbols, all retained with probability at most (m/n)r(m/n)^r. The expected number retained is at most 2qtnr−1(m/n)r=o(1)2qtn^{r-1}(m/n)^r=o(1) for a minimum colouring, since q=O(logn)q=O(\log n). Thus there is a choice on which no exceptional edge survives. The palettes properly colour Sr−1(m)S_{r-1}(m) with at most 2q2^q colours, so q≥log2χ(Sr−1(m))q\ge\log_2\chi(S_{r-1}(m)).

For completeness, a proper colouring of Sr(n)S_r(n) gives disjoint incoming and outgoing colour sets at each junction. Taking the outgoing sets gives a proper colouring of Sr−1(n)S_{r-1}(n) with at most 2χ(Sr(n))2^{\chi(S_r(n))} colours. Conversely, from a proper CC-colouring of Sr−1(n)S_{r-1}(n) assign distinct equal-cardinality subsets of [b][b] as palettes for the CC colours, with (b⌊b/2⌋)≥C\binom{b}{\lfloor b/2\rfloor}\ge C. 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 Sr(n)S_r(n). Since one can choose b=log2C+O(log2log2(C+2)+1)b=\log_2 C+O(\log_2\log_2(C+2)+1), induction gives the stated asymptotic for χ(Sr(n))\chi(S_r(n)), and in particular the O(logn)O(\log n) upper bounds used above. The palette lower bound also gives log2χ(Sr−1(m))≥log2(r−1)m=log2(r−1)n−Or(1)\log_2\chi(S_{r-1}(m))\ge\log_2^{(r-1)}m=\log_2^{(r-1)}n-O_r(1) for r≥3r\ge3. A dicolouring must avoid monochromatic directed four-cycles, so the same lower bounds apply to δ(Sr(n))\delta(S_r(n)).

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 tt as a set Cv⊆[0,t)C_v\subseteq[0,t) of measure one for each vertex vv, 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 S⊆V(G)S\subseteq V(G) put C(S)=⋃v∈SCvC(S)=\bigcup_{v\in S}C_v. 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 C(S)C(S) 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 BkB_k of Felsner et al., χf(B1)=1\chi_f(B_1)=1 and χf(Bk)=(k+2)/2\chi_f(B_k)=(k+2)/2 for k≥2k\ge2. Indeed, put sk=(k+1)/2s_k=(k+1)/2. The recursion starts at a single vertex with that singleton as the distinguished stable set. It uses a master copy of BkB_k and, for each distinguished set SS in the master, another copy of BkB_k. For each distinguished set XX in that other copy it adds a vertex vS,Xv_{S,X} adjacent to exactly XX. The new distinguished sets are S∪XS\cup X and S∪{vS,X}S\cup\{v_{S,X}\}.

Inductively every fractional colouring of BkB_k has a distinguished set SS with |C(S)|≥sk|C(S)|\ge s_k. For the step, take such an SS in the master and such an XX in its associated copy. If |C(S)∪C(X)|≥sk+1/2|C(S)\cup C(X)|\ge s_k+1/2, we are done. Otherwise |C(S)\C(X)|<1/2|C(S)\setminus C(X)|\lt1/2, and the palette of vS,Xv_{S,X} is disjoint from C(X)C(X). Consequently |C(S)∪CvS,X|>sk+1/2|C(S)\cup C_{v_{S,X}}|\gt s_k+1/2. This establishes the induction and also gives χf(Bk+1)≥sk+1\chi_f(B_{k+1})\ge s_k+1, since the palette for vS,Xv_{S,X} avoids C(X)C(X) of measure at least sks_k.

For the upper bound, we maintain a colouring of BkB_k of palette length wkw_k with every distinguished set having union measure exactly sks_k. Take w1=1w_1=1 and wk=sk+1/2w_k=s_k+1/2 for k≥2k\ge2. For the step set s=sks=s_k and use a palette of length s+1s+1, placing the master colouring unchanged. For every master set SS, split the palette of its associated copy in the ratios 1−1/(2s)1-1/(2s) and 1/(2s)1/(2s), placing the first part inside C(S)C(S) and the second outside. This fits since wk≤s+1/2w_k\le s+1/2, so the two lengths are at most s−1/(4s)s-1/(4s) and 1/2+1/(4s)1/2+1/(4s), respectively. Thus every copy probe XX has |C(X)\C(S)|=1/2|C(X)\setminus C(S)|=1/2 and |C(X)∩C(S)|=s−1/2|C(X)\cap C(S)|=s-1/2. The remaining palette outside C(X)C(X) has measure 1/21/2 inside C(S)C(S) and 1/21/2 outside C(S)C(S). Give it all to vS,Xv_{S,X}. Now both new distinguished sets have palette union measure s+1/2s+1/2. This gives the asserted colouring of Bk+1B_{k+1}, of palette length s+1=wk+1s+1=w_{k+1}.

Twincut graphs. For a rooted tree with hh levels, start at a single root. At level j≥2j\ge2 the children of every node at level j−1j-1 induce a copy of the same graph HjH_j. 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 tj=χf(Hj)t_j=\chi_f(H_j) and define

s1=1,sj=sj−1+max{0,1−sj−1/tj}.s_1=1,\qquad s_j=s_{j-1}+\max\{0,1-s_{j-1}/t_j\}.

Then the fractional chromatic number of this graph is max(max2≤j≤htj,1+sh)\max(\max_{2\le j\le h}t_j,1+s_h), with the first maximum omitted at height one.

For the lower bound, consider a branch prefix whose palettes have union UU of measure uu. Among the children in its next sibling graph HjH_j, there is a vertex with |Cv∩U|≤u/tj|C_v\cap U|\le u/t_j. Otherwise all restricted palettes could be scaled by the reciprocal of their minimum measure to give a fractional colouring of HjH_j of length strictly smaller than tjt_j. The new palette union is therefore at least u+max{0,1−u/tj}u+\max\{0,1-u/t_j\}. This function is nondecreasing in uu because tj≥1t_j\ge1. Starting at the root, one can find a full branch of union measure at least shs_h. Its branch vertex needs a disjoint palette of measure one. Each HjH_j is a subgraph, giving the other lower bound.

Conversely, use a palette of length q=max(maxjtj,1+sh)q=\max(\max_jt_j,1+s_h). Give the root any palette of measure one. At each next sibling graph split an optimal palette of length tjt_j to place length min(tj,sj−1)\min(t_j,s_{j-1}) within the ancestor union and the rest outside. This fits since sj−1≤shs_{j-1}\le s_h and q≥tjq\ge t_j. For every child the palette union along its branch prefix then has measure exactly sjs_j. The complement of any full branch's union has measure at least one and supplies its branch vertex.

For the twincut graph GkG_k, the tree has height k−1k-1, and for levels 2≤j≤k−12\le j\le k-1 its sibling graphs are copies of GjG_j. Thus ak=χf(Gk)a_k=\chi_f(G_k) satisfies a1=1a_1=1 and ak+1=ak+1/aka_{k+1}=a_k+1/a_k. In detail, s1=1=a2−1s_1=1=a_2-1, and if sj−1=aj−1s_{j-1}=a_j-1 then sj=aj−1+1/aj=aj+1−1s_j=a_j-1+1/a_j=a_{j+1}-1. Squaring the recurrence gives ak+12=ak2+2+ak−2a_{k+1}^2=a_k^2+2+a_k^{-2}, so ak2=2k+O(logk)a_k^2=2k+O(\log k).

Mohar and Wu give a maximum dichromatic number of order at least t/logtt/\log t when t=χft=\chi_f. It follows that δ(Bk)=Ω(k/logk)\delta(B_k)=\Omega(k/\log k) and δ(Gk)=Ω(k/logk)\delta(G_k)=\Omega(\sqrt{k}/\log k). 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 C4C_4-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 DD be a finite simple digraph partitioned into nonempty sets V1,…,VmV_1,\ldots,V_m, with all arcs going from a lower to a higher index. Suppose its maximum outdegree is at most d≥1d\ge1. Write L(D)L(D) for the undirected graph of its arcs, adjacent when consecutive in a directed path. Give each vertex of ViV_i weight 1/|Vi|1/|V_i|. Suppose each independent set of the underlying graph of DD has total weight at most m/Tm/T. For an integer q≥1q\ge1, assume

|Vi|≥4dlog2(2qd)∑j>i|Vj|(i<m),t=⌈log2(1024qd(d+1))⌉.|V_i|\ge 4d\log_2(2qd)\sum_{j>i}|V_j|\quad(i<m), \qquad t=\left\lceil\log_2(1024qd(d+1))\right\rceil .

If (3/4)T>2q(q(t−1)+1)(3/4)T\gt 2^q(q(t-1)+1), then L(D)L(D) has an orientation in which every qq-colouring has a monochromatic directed four-cycle.

Proof. Orient the edges of L(D)L(D) independently at random. Consider a vertex vv of DD and any choice of colours and a linear order on its outgoing arcs. Call an incoming arc ee compatible if for some colour with at least tt outgoing arcs, its forward edges in the orientation of L(D)L(D) to those arcs form a suffix in their order. The signs for the rr edges from ee to an outgoing block of size rr are uniform on 2r2^r possibilities, of which r+1r+1 are suffixes. Thus the chance that ee is compatible is at most q(d+1)2−tq(d+1)2^{-t}.

Fix a layer ViV_i and fix the choices of colours and orders at vertices in the higher layers. For u∈Viu\in V_i, call uu bad if any arc out of uu is compatible at its head. The probability of this is at most dq(d+1)2−t≤2−10dq(d+1)2^{-t}\le2^{-10}. These events are independent across u∈Viu\in V_i, because different incoming arcs at each junction use disjoint sets of edges of L(D)L(D). For ni=|Vi|n_i=|V_i| the probability of at least ni/4n_i/4 bad vertices is at most 2ni(2−10)ni/4=2−3ni/22^{n_i}(2^{-10})^{n_i/4}=2^{-3n_i/2}. Over all vertices in higher layers the number of choices of colours and orders is at most (qdd!)∑j>inj≤2ni/4(q^d d!)^{\sum_{j>i}n_j}\le 2^{n_i/4}. The failure probability on each layer i<mi<m is thus at most 2−ni2^{-n_i}, and these bounds sum to less than one because the nin_i 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 qq-colouring of the arc vertices with no monochromatic directed four-cycle. For every junction vv 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 tt outgoing arcs is now compatible at that junction. Retain the good vertices of DD for these choices. Their combined weight is at least (3/4)m(3/4)m.

At a retained vertex vv let P(v)P(v) be the set of colours with at least tt outgoing arcs in the original DD. An arc u→vu\to v with both endpoints retained and P(u)=P(v)P(u)=P(v) must have colour outside this common palette. If its colour belonged to the palette at vv, uu would be bad. There are at most q(t−1)q(t-1) 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 q(t−1)q(t-1) and is (q(t−1)+1)(q(t-1)+1)-colourable by reverse topological order. Over at most 2q2^q palettes this gives at most 2q(q(t−1)+1)2^q(q(t-1)+1) independent sets partitioning the retained vertices. Their total weight cannot reach (3/4)m(3/4)m under the given bound on TT. This contradiction proves the assertion.

The proof of Nguyen and Walczak's Theorem 2.1 supplies such a base DD for arbitrarily large TT, with d=O(T2logT)d=O(T^2\log T) 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 d+(d2)d+\binom d2 there for their 3-colourability conclusion on C4C_4-free subgraphs of L(D)L(D). Our orientation gives the simultaneous lower bound

δ(L(D))≥log2T−2log2log2T−O(1),\delta(L(D))\ge \log_2 T-2\log_2\log_2 T-O(1),

by taking q=⌊log2T−2log2log2T−C⌋q=\lfloor\log_2 T-2\log_2\log_2 T-C\rfloor for a sufficiently large constant CC. Meanwhile χf(L(D))≤4\chi_f(L(D))\le4, since independent fair bits assigned to the base vertices select each arc with probability 1/41/4 as a 00-to-11 arc, and these selected arcs always form an independent set of L(D)L(D).

Iterated generalized Mycielski graphs

A generalized Mycielski step of height m≥1m\ge1 replaces a graph FF by layers 0,…,m0,\ldots,m of copies of its vertices and adds an apex adjacent to the last layer. An edge of FF is copied within layer zero and across each pair of successive layers. Write χs(F)\chi_s(F) for the minimum palette size of a proper ss-fold colouring, where every vertex receives ss 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 FF, after χs(F)\chi_s(F) further generalized Mycielski steps of arbitrary positive heights, the result contains the induced blow-up of FF with 2s2^s 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 ss-fold colouring of FF one at a time, doubling all current copies of each vertex in the corresponding independent set. Each original vertex gets doubled exactly ss times.

When FF has no isolated vertices, χs(F)\chi_s(F) 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 FF. To see this, index a descendant by its sequence of layer numbers. For original neighbours u,vu,v, at each coordinate every layer occupied by the fibre of uu must be adjacent to every layer occupied by the fibre of vv 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 FF. Each fibre of order 2s2^s needs at least ss such coordinates. The coordinates give an ss-fold colouring after discarding excess memberships.

Consequence for orientations. If χ(F)>q\chi(F)\gt q, the blow-up with fibre size bb can be oriented so that every qq-colouring contains a monochromatic directed cycle of length four, provided b≥Cqlog(2q)b\ge Cq\log(2q) for a sufficiently large constant CC. 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 ⌈b/q⌉\lceil b/q\rceil 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 qq-colouring of FF 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 F0=K2F_0=K_2, Stiebitz's theorem gives χ(Fi)=i+2\chi(F_i)=i+2. Taking q=i+1q=i+1 and s=O(log(i+2))s=O(\log(i+2)) so that 2s≥Cqlog(2q)2^s\ge Cq\log(2q), we have χs(Fi)≤s(i+2)\chi_s(F_i)\le s(i+2). The graph at step tt therefore has an orientation requiring Ω(t/log(t+2))\Omega(t/\log(t+2)) 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 2s2s raises χs\chi_s by at most one. Any step raises it by at most ss, by keeping the original ss-fold colouring in every layer and using ss new colours at the apex. If Bi(s)B_i(s) is the number of heights below 2s2s among the first ii steps from K2K_2, then

χs(Fi)≤2s+i+(s−1)Bi(s).\chi_s(F_i)\le 2s+i+(s-1)B_i(s).

In particular, if the height mjm_j at step jj satisfies mj/log(j+1)→∞m_j/\log(j+1)\to\infty, then for the preceding choice s=O(logi)s=O(\log i) we have Bi(s)=O(i)B_i(s)=O(\sqrt i). Indeed, all j≥ij\ge\sqrt i have heights at least 2s2s once ii is sufficiently large. After 2i+o(i)2i+o(i) total steps we can force i+2i+2 colours to avoid monochromatic directed four-cycles. Thus the lower bound along these sequences is (1/2−o(1))χ(Ft)(1/2-o(1))\chi(F_t). Pan–Zhu

For example, heights mj=jm_j=j also allow bounded fractional chromatic number. Tardif's formula says the fractional increment at height mm is 1/∑ℓ=0m(χf−1)ℓ1/\sum_{\ell=0}^m(\chi_f-1)^\ell, with χf\chi_f measured before the step. The first step is C5C_5, with χf=5/2\chi_f=5/2. All subsequent increments are bounded by (2/3)j(2/3)^j, 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