(Claw, C → 3 \vec{C}_{3} )-free Digraphs with Unbounded Dichromatic Number Guillaume Aubian, Luis Kuffner Abstract . We construct orientations of rook graphs (whose underlying graphs are claw-free) that contain no C → 3 \vec{C}_{3} but have unbounded dichromatic number. This disproves a conjecture of Aboulker, Charbit and Naserasr and improves a result of Carbonero, Koerts, Moore and Spirkl. 1. Introduction and notation A hero is a tournament H such that tournaments not containing H have bounded dichromatic number. In a seminal paper [ 3 ] , Berger, Choromanski, Chudnovski, Fox, Loebl, Scott, Seymour and Thomassé obtained a structure theorem for heroes. Harutyunyan, Le, Newman and Thomassé [ 7 ] later proved that oriented graphs with bounded independence number (tournaments being the special case where the independence number equals one) not containing a hero have bounded dichromatic number. Chudnovsky, Scott and Seymour [ 6 ] subsequently showed that for any transitive tournament H and oriented star S , oriented graphs containing neither S nor H as induced subdigraphs have bounded dichromatic number. Aboulker, Charbit and Naserasr [ 2 ] thus wondered whether (and actually conjectured that), for any hero H and any oriented star forest S , oriented graphs containing neither S nor H as induced subdigraphs have bounded dichromatic number. Aboulker, Aubian and Charbit [ 1 ] provided a counterexample when S=K_{1}+\vec{K}_{2} . Carbonero, Koerts, Moore and Spirkl [ 5 ] did so when H=\Delta(1,1,C_{3}) and S is any orientation of K_{1,4} , and also when H=\vec{C}_{3} and S is any orientation of K_{1,5} . We improve these two latter results with a counterexample when H=\vec{C}_{3} and S is any orientation of K_{1,3} , i.e. the claw. Definitions in this paper are standard and follow from Bondy and Murty’s book [ 4 ] . In this paper, we study oriented graphs, i.e. directed graphs with no pair of opposite arcs. Given two integers n,i\geq 0 , we write n_{i} for the i th least significant bit of the binary expansion of n , starting from i=0 . 2. Construction and proof Let N be a positive integer. The N\times N rook graph R_{N} is the graph with vertex set [1,N]^{2} and with an edge between two vertices whenever they share their first coordinate or they share their second coordinate. Intuitively, it is the graph describing how a rook moves on a N\times N chessboard. It is the line graph of K_{N,N} , and therefore is claw-free. We orient it into a digraph D_{N} as follows. For any vertices (a,b),\ (a,d),\ (c,b) , we orient the edge from (a,b) to (a,d) if and only if b_{i}=a_{i} , where i=\min\{j\mid b_{j}\neq d_{j}\} , and we orient the edge from (a,b) to (c,b) if and only if b_{i}\neq a_{i} , where i=\min\{j\mid a_{j}\neq c_{j}\} . Proposition 1 . The digraph D_{N} contains no \vec{C}_{3} . Proof. Given three vertices (a,b) , (a,c) and (a,d) on the same row, let i=\min\{j\mid\{b_{j},c_{j},d_{j}\}=\{0,1\}\} . Without loss of generality let us assume that b_{i}\neq c_{i}=d_{i} . Edges (a,b)(a,c) and (a,b)(a,d) are oriented only depending on whether a_{i}=b_{i} and thus have the same orientation. Thus, (a,b) , (a,c) and (a,d) can not form a \vec{C}_{3} . The same argument applies to any column. Since every triangle in a rook graph is contained entirely in a single row or in a single column, D_{N} contains no \vec{C}_{3} . ∎ Lemma 1 . When |a-c|=|b-d| , vertices (a,b),\ (a,d),\ (c,d),\ (c,b) induce a directed 4 -cycle. Proof. Let i=\min\{j\mid|a-c|_{j}=1\} . Then i=\min\{j\mid a_{j}\neq c_{j}\}=\min\{j\mid b_{j}\neq d_{j}\} . Up to permuting a and c and/or permuting b and d , we may assume a_{i}=b_{i}=1 and c_{i}=d_{i}=0 . Since b_{i}=a_{i} , we have (a,b)\to(a,d) . Since d_{i}\neq a_{i} , we have (a,d)\to(c,d) . Since d_{i}=c_{i} , we have (c,d)\to(c,b) . Since b_{i}\neq c_{i} , we have (c,b)\to(a,b) . Thus the four vertices form the directed cycle (a,b)\to(a,d)\to(c,d)\to(c,b)\to(a,b) . ∎ Note that it actually suffices that d_{2}(a,c)=d_{2}(b,d) where d_{2} is the dyadic distance, but this stronger condition suffices for the sake of our result. Theorem 1 . The family (D_{N})_{N\geq 1} has unbounded dichromatic number. Proof. Fix k . The Gallai–Witt theorem [ 8 ] (also known as the multidimensional van der Waerden theorem) implies that there exists N such that any k -colouring of [1,N]^{2} contains a monochromatic axis-parallel square, that is, four points of the form (x,y),\ (x+t,y),\ (x,y+t),\ (x+t,y+t) for some integers x,y,t>0 . Thus, for N large enough, any colouring of V(D_{N}) with k colours contains a monochromatic square as above. By the previous lemma, the four vertices of such a square induce a directed 4 -cycle. Hence, some colour class does not induce an acyclic subdigraph. Since k is arbitrary, the dichromatic number of D_{N} is unbounded. ∎