# Chordal Directed Graphs Are Not χ-Bounded

Pierre Aboulker, Nicolas Bousquet, Rémi de Verclos

► To cite this version:

Pierre Aboulker, Nicolas Bousquet, Rémi de Verclos. Chordal Directed Graphs Are Not χ-Bounded. The Electronic Journal of Combinatorics, 2022, 29 (2), 10.37236/11050. hal-03829690

HAL Id: hal-03829690

https://hal.science/hal-03829690v1

Submitted on 21 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Chordal directed graphs are not directed $\chi$-bounded

Pierre Aboulker *

DIENS, École normale supérieure
CNRS, PSL University
Paris, France
pierreaboulker@gmail.com

Nicolas Bousquet †

Univ. Lyon, Université Lyon 1
LIRIS, UMR CNRS 5205, F-69621
Lyon, France
nicolas.bousquet@univ-lyon1.fr

Rémi de Verclos

remi.de.joannis.de.verclos@ens-lyon.org

Submitted: Feb 12, 2022; Accepted: Apr 2, 2022; Published: May 6, 2022

© The authors. Released under the CC BY-ND license (International 4.0).

## Abstract

We show that digraphs with no transitive tournament on 3 vertices and in which every induced directed cycle has length 3 can have arbitrarily large dichromatic number. This answers in the negative a question of Carbonero, Hompe, Moore, and Spirkl (and strengthens one of their results).

**Mathematics Subject Classifications:** 05C15, 05C20

## 1 Introduction

Throughout this paper, we only consider simple graphs (resp. directed graphs) $G$, that is, for every two distinct vertices $u$ and $v$, the graph $G$ does not have multiple edges (resp. both arcs $uv$ and $vu$).

Relations between the chromatic number $\chi(G)$ and the clique number $\omega(G)$ of a graph $G$ have been studied for decades in structural graph theory. In particular, it is well known that there exist triangle-free graphs $G$ with arbitrarily large chromatic number (see e.g. [4, 9]). A hereditary class of graphs is $\chi$-bounded if there exists a function $f$ such that for every $G \in \mathcal{G}$, $\chi(G) \le f(\omega(G))$ (see e.g. a recent survey [7] on the topic). The following question received considerable attention in the last few years: Consider a hereditary class of graphs $\mathcal{G}$ in which every triangle-free graph has bounded chromatic number. Is it true that $\mathcal{G}$ is $\chi$-bounded? Carbonero, Hompe, Moore and Spirkl [2] answered this in the negative in a recent breakthrough paper.

Their initial motivation was actually to prove a result on digraphs. Let $D$ be a digraph. A $k$-dicolouring of $D$ is a $k$-partition $(V_1, \dots, V_k)$ of $V(D)$ such that $D[V_i]$ is acyclic for every $1 \le i \le k$. Such a partition is also called an *acyclic colouring of $D$*. The *dichromatic number of $D$*, denoted by $\vec{\chi}(D)$ and introduced by Neumann-Lara in [6], is the smallest integer $k$ such that $D$ admits a $k$-dicolouring. We denote by $\omega(D)$ the size of a largest clique in the underlying graph of $D$. A *directed triangle* is a directed cycle of length 3. As for unoriented graphs, we say that a hereditary class of digraphs $\mathcal{G}$ is *$\vec{\chi}$-bounded* if for every $G \in \mathcal{G}$, $\vec{\chi}(G) \le f(\omega(G))$.

Carbonero, Hompe, Moore and Spirkl [2] proved that the class of digraphs with no induced directed cycle of odd length at least 5 is not $\vec{\chi}$-bounded by giving a collection of digraphs with no induced directed cycle of odd length at least 5, no $K_4$ and with arbitrarily large dichromatic number. They ask (Question 3.2) if the class of digraphs in which every induced directed cycle has length 3 is $\vec{\chi}$-bounded. These digraphs can be seen as directed analogues of chordal graphs, where a *chordal directed graph* is a directed graph with no induced directed cycle of length at least 4.

<footnote>*Supported by ANR project DAGDigDec (JCJC) ANR-21-CE48-0012</footnote>

<footnote>†Supported by ANR project DAGDigDec (JCJC) ANR-21-CE48-0012</footnote>
We give a negative answer to this question (and thus strengthen the construction of [2]). Let us denote by $TT_3$ the transitive tournament on 3 vertices (i.e. the triangle which is oriented acyclically). Let $C_3$ be the class of digraphs with no $TT_3$ nor induced directed cycle of length at least 4. We prove the following.

**Theorem 1.** For every $k$, there exists $G \in C_3$ such that $\vec{\chi}(G) \ge k$.

Since any orientation of a $K_4$ contains a $TT_3$, Theorem 1 answers Question 3.2 of [2].

## 2 Proof of Theorem 1

Our proof technique can be seen as a generalization of the construction of triangle-free graphs with arbitrarily large chromatic number due to Zykov [9]. Assume that we are given a triangle-free graph $G_k$ with chromatic number at least $k$, and let us define $G_{k+1}$ as follows (note that we can set $G_1$ as a single vertex graph). Let $G$ be the graph made of $k$ disjoint induced copies of $G_k$. Set $\mathcal{I}$ to be the set of all $k$-subsets of vertices of $G$ containing exactly one vertex in each copy of $G_k$. Now, build the graph $G_{k+1}$ from $G$ as follows: for every set $I \in \mathcal{I}$, create a new vertex $x_I$ adjacent to every vertex in $I$. The key observation is that, for any colouring of $G_{k+1}$, for each $I \in \mathcal{I}$, the vertex $x_I$ forces $I$ to miss at least one colour, namely the one received by $x_I$. This easily implies that $G_{k+1}$ is not $k$-colourable. Indeed, if one tries to $k$-colour $G_{k+1}$, since $G_k$ has chromatic number $k$, there must be a vertex $x_i$ coloured $i$ in the $i^{th}$ copy of $G_k$ for every $i \le k$. A contradiction with the key observation above. Moreover, since each set of $\mathcal{I}$ is an independent set, $G_{k+1}$ is triangle-free.

For digraphs, such a naive construction fails since adjacent vertices are allowed to receive the same colour. A way to force a given independent set $I$ of a digraph $D$ to avoid a colour (without creating induced directed cycle of length at least 4 nor $TT_3$) is to connect each vertex of $I$ to an arc $uv$ (instead of a single vertex as in the directed case) in such a way that each vertex of $I$ forms a directed triangle with $uv$ and then hope that the two vertices $u$ and $v$ receive the same colour. Unfortunately we cannot force an arc to have both endpoints of the same colour. But we have the following slightly weaker property.

**Remark 2.** Let $G \in C_3$ be a directed graph with at least one arc. Any $\vec{\chi}(G)$-dicolouring of $G$ contains at least one monochromatic arc.

*Proof.* The result trivially holds if $\vec{\chi}(G) = 1$, so we may assume that $\vec{\chi}(G) \ge 2$. Let $V_1, \dots, V_{\vec{\chi}(G)}$ be a $\vec{\chi}(G)$-dicolouring of $G$. The set $V_1 \cup V_2$ must contain an induced directed cycle $C$ since otherwise $G$ would be $(\vec{\chi}(G) - 1)$-colourable. (Indeed, a colouring of the vertices of a digraph is acyclic if and only if none of its induced directed cycles is monochromatic). Hence, by definition of $C_3$, $V_1 \cup V_2$ contains a directed triangle, and an arc of this directed triangle must have both endpoints in $V_1$ or both endpoints in $V_2$. $\square$

Let $G$ be a $k$-chromatic digraph and $I$ be an independent set of $G$. Using Remark 2, we prove that we can create a graph $G'$ containing many induced copies of $G$ such that, for every $k$-coloring of $G'$, there is one copy of $G$ in $G'$ where the vertices of $I$ (in that copy) miss at least one color (Lemma 3). We then extend this result for arbitrarily many independent sets (Lemma 4). We then prove Theorem 1 using Lemma 4 as in Zykov's construction.

**Lemma 3.** Let $k$ be an integer. Let $G \in C_3$ with $n$ vertices and $m$ arcs, and such that $\vec{\chi}(G) = k$. Let $I$ be an independent set of $G$. Then there exists a digraph $H \in C_3$ such that $H$ contains $m$ pairwise disjoint induced copies $G_1, \dots, G_m$ of $G$ and satisfy the following:

* For every $1 \le i \ne j \le m$, there is no arc between $G_i$ and $G_j$;

* For every $k$-dicolouring of $H$, there exists an index $i \le m$ and a colour $\alpha \in \{1, \dots, k\}$ such that no vertex of the copy of $I$ in $G_i$ is coloured with $\alpha$.

Moreover $H$ has $n \cdot (m+1) \le n^4$ vertices and at most $m(m+1) + mn^2 \le n^4$ arcs.
*Proof.* Let us first describe the construction of $H$. We first create $m+1$ pairwise disjoint induced copies of $G$ denoted by $G_1, \dots, G_m, G_{m+1}$. For every $i \le m$, let $I_i$ be the copy of $I$ in $G_i$. Let us denote $u_1^{m+1}v_1^{m+1}, \dots, u_m^{m+1}v_m^{m+1}$ the arcs of $G_{m+1}$. We add in $H$ some arcs between the $G_i$ ($i \le m$) and $G_{m+1}$ as follows. For every $i \le m$ and for every vertex $x \in I_i$, add the arcs $v_i^{m+1}x$ and $xu_i^{m+1}$ in $H$.

Observe that $H$ has $n \cdot (m+1)$ vertices and $m \cdot (m+1) + 2m \cdot |I| \le n^4$ arcs as announced.

By construction, for every $1 \le i \ne j \le m$, there is no arc between $G_i$ and $G_j$, so the first bullet holds.

Let $c$ be a $k$-dicolouring of $H$. By Remark 2, $G_{m+1}$ has a monochromatic arc, say $u_i^{m+1}v_i^{m+1}$. Let $\alpha$ be the colour of $u_i^{m+1}$ and $v_i^{m+1}$ in $c$. Then, for every vertex $x \in I_i$, $x$ is not coloured with $\alpha$ since $H[\{u_i, v_i, x\}]$ is a directed triangle. This proves the second bullet.

To conclude, we simply have to prove that $H \in C_3$. First assume for contradiction that $H$ contains a copy $X$ of a $TT_3$ as a subgraph. Since there is no arc between $G_i$ and $G_j$ for $1 \le i \ne j \le m$, $X$ intersects at most one of the graphs $G_i$ for $i \le m$. Moreover, since $G$ is in $C_3$, $X$ is not included in $G_i$ for $i \le m+1$. So $X$ must intersect $G_{m+1}$ and $G_i$ for some $i \le m$. Assume first that $X$ contains two vertices of $G_{m+1}$. By construction, the only vertices of $G_{m+1}$ connected to $G_i$ are $u_i^{m+1}$ and $v_i^{m+1}$. So both vertices are in $X$. Moreover, the only vertices of $G_i$ connected to $G_{m+1}$ are the vertices of $I_i$ so the third vertex must be a vertex $x$ of $I_i$. But by construction, $G[\{x, u_i^{m+1}, v_i^{m+1}\}]$ is a directed triangle, a contradiction. So we can assume that $X$ contains two vertices of $G_i$. Since $X$ is a $TT_3$, they must be adjacent and both be adjacent to a vertex of $G_{m+1}$. But, by construction, the only vertices of $G_i$ connected to $G_{m+1}$ are the vertices of $I_i$ which is an independent set, a contradiction. So $H$ contains no $TT_3$.

Finally, assume for contradiction that $H$ contains a directed cycle $C$ of length at least 4 as an induced subgraph. Since $G \in C_3$, $C$ is not contained in $G_i$ for $i = 1, \dots, m+1$. Since there is no arc between $G_i$ and $G_j$ for $1 \le i \ne j \le m$, the cycle $C$ intersects $G_{m+1}$ and we may assume without loss of generality that $C$ also intersects $G_1$. So $C$ contains $u_1^{m+1}$ or $v_1^{m+1}$. Since, by construction, $u_1^{m+1}$ has no out-neighbour in $G_1$ and $v_1^{m+1}$ has no in-neighbour in $G_1$, $C$ must contain both $u_1^{m+1}$ and $v_1^{m+1}$ (since the deletion of $u_1^{m+1}$ and $v_1^{m+1}$ disconnects $G_1$ from the rest of the graph). But now all the vertices of $G_1$ incident to $u_1$ or $v_1$ are the vertices $x$ of $I$. And by construction, for every $x \in I$, $H[\{u_1^{m+1}, v_1^{m+1}, x\}]$ is a directed triangle, a contradiction.
$\square$

**Lemma 4.** Let $k, r$ be two integers. Let $G \in C_3$ such that $\vec{\chi}(G) = k$ and let $I_1, \dots, I_r$ be $r$ independent sets of $G$. There exist an integer $\ell_r$ and a digraph $H \in C_3$ such that $H$ contains $\ell_r$ pairwise disjoint induced copies $G_1, \dots, G_{\ell_r}$ of $G$ such that:

* For every $1 \le i \ne j \le \ell_r$, there is no arc between $G_i$ and $G_j$;

* For every $k$-dicolouring of $H$, there exists an index $j \le \ell_r$ such that, for every $s \le r$, there exists a colour $\alpha_s \in \{1, \dots, k\}$ such that no vertex of the copy of $I_s$ in $G_j$ is coloured with $\alpha_s$.

Moreover $H$ contains at most $n^{4r}$ vertices and arcs.

*Proof.* We now have all the ingredients to prove Lemma 4 by induction on $r$. By Lemma 3, the case $r=1$ holds.

Assume that the conclusion holds for $r \ge 1$ and let us prove the result for $r+1$. Let $G \in C_3$ with $\vec{\chi}(G) = k$ and let $I_1, \dots, I_{r+1}$ be $r+1$ independent sets of $G$. By induction applied to $G$ and independent sets $I_1, \dots, I_r$, there exists an integer $\ell_r$ and a digraph $H_r \in C_3$ such that $H_r$ contains $\ell_r$ pairwise disjoint induced copies $G_1, \dots, G_{\ell_r}$ of $G$ such that:

* For every $1 \le i \ne j \le \ell_r$, there is no arc between $G_i$ and $G_j$;

* For every $k$-dicolouring of $H_r$, there exists an index $j \le \ell_r$ such that, for $s = 1, \dots, r$, there exists a colour $\alpha_s$ such that no vertex of the copy of $I_s$ in $G_j$ is coloured with $\alpha_s$.

Note that by induction, $H_r$ has at most $n^{4r}$ vertices and edges. Let us denote by $J$ the union of the vertices of the copies of $I_{r+1}$ in the subgraphs $G_1, \dots, G_{\ell_r}$ and observe that $J$ is an independent set. By Lemma 3 applied to $H_r$ and $J$, there exists a digraph $H_{r+1} \in C_3$ that contains $m = |E(H_r)|$ pairwise disjoint induced copies $H_r^1, \dots, H_r^m$ of $H_r$ such that:
• For $1 \le i \ne j \le m$, there is no arc between $H_r^i$ and $H_r^j$;

• For every $k$-dicolouring of $H_{r+1}$, there exists an index $j \le m$ and a colour $\alpha_{r+1}$ such that no vertex of the copy of $J$ in $H_r^j$ is coloured with $\alpha_{r+1}$.

Moreover, $H$ has at most $|V(H_r)|^4 = n^4(r+1)$ vertices and arcs.

Let us prove that $H_{r+1}$ satisfies the conclusion of Lemma 4. For every $i \le m$, $H_r^i$ being an induced copy of $H_r$, it contains $\ell_r$ pairwise disjoint induced copies of $G$, denoted by $G_1^i, \dots, G_{\ell_r}^i$. Thus, by construction of $H_{r+1}$, the graph $H_{r+1}$ contains $\ell_{r+1} := m \cdot \ell_r$ induced copies of $G$ and by construction there is no arc linking any of these copies.

Fix a $k$-dicolouring of $H_{r+1}$. There exists an index $j \le m$ and a colour $\alpha_{r+1}$ such that no vertex of the induced copy of $J$ in $H_r^j$ is coloured $\alpha_{r+1}$. Since $H_r^j$ is an induced copy of $H_r$ there exists an index $k \le \ell_r$ such that, for $s = 1, \dots, r$, there exists a colour $\alpha_s$ such that no vertex of the induced copy of $I_s$ in $G_k^j$ is coloured with $\alpha_s$. Hence, the second bullet holds, which completes the proof. $\square$

*Proof of Theorem 1.* Let us construct a sequence $(G_k)_{k \in \mathbb{N}}$ such that for every $k$, $G_k \in C_3$ and $\tilde{\chi}(G_k) \ge k$. Let $G_1$ be the graph consisting of a single vertex and let $G_2$ be the directed triangle. Let $k \ge 2$ and assume that we have obtained a $k$-dichromatic digraph $G_k$ which is in $C_3$, let us define $G_{k+1}$ as follows. Let $G$ be the digraph consisting of $k$ pairwise disjoint induced copies of $G_k$, denoted by $G_k^1, \dots, G_k^k$. Let $\mathcal{I}$ be the set of independent sets that intersect each $G_k^i$ in a single vertex. Since $\tilde{\chi}(G_k) \ge k$, in any $k$-dicolouring of $G$, there exists a vertex $x_i$ coloured $i$ in $G_k^i$ for every $i = 1, \dots, k$. By definition of $\mathcal{I}$, $\{x_1, \dots, x_k\} \in \mathcal{I}$. Hence, for every $k$-dicolouring of $G$, a set of $\mathcal{I}$ receives all the colours.

By Lemma 4 applied to $G$ and $\mathcal{I}$, there exists a digraph $G_{k+1} \in C_3$ such that, for every $k$-dicolouring of $G_{k+1}$ (if such a colouring exists), there exists an induced copy of $G$ in $G_{k+1}$ such that each set $\mathcal{I}$ in that copy of $G$ avoids a colour, a contradiction. So $\tilde{\chi}(G_{k+1}) \ge k+1$. $\square$

# 3 Further works

Our $(k+1)$-dichromatic graph $G_{k+1}$ has size $|G_k|^{2^{poly(|G_k|)}}$, which is larger than the graphs obtained using Zykov's construction which have size of order $2^{poly(|G_k|)}$. It would be interesting to know if the size of our example can be reduced.

One can wonder if directed triangles play a particular role in Theorem 1. More formally, one can wonder (as also asked in [2], Question 3.3) for which integer $k$, the class of digraphs which only contain induced directed cycles of length exactly $k$ are $\tilde{\chi}$-bounded? Our main result is that it is not the case for $k=3$. Based on the idea of our construction, Carborero et al. [3] very recently answered in the negative this question for any possible value of $k$.

On the same flavour, we recall here the following conjecture of Aboulker, Charbit and Naserasr which can be seen as a directed analogue of the well-known Gyárfás-Sumner conjecture [5, 8]. An *oriented tree* is an orientation of a tree.

**Conjecture 5.** [1] For every oriented tree $T$, the class of digraphs with no induced $T$ is $\tilde{\chi}$-bounded.

# Acknowledgments

This research was supported by ANR project DAGDigDec (JCJC) ANR-21-CE48-0012.

# References

[1] P. Aboulker, P. Charbit, and R. Naserasr. Extension of Gyárfás-Sumner conjecture to digraphs. *The Electronic Journal of Combinatorics*, 18(2):#P2.27, 2021.

[2] A. Carbonero, P. Hompe, B. Moore, and S. Spirkl. A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number. arXiv:2201.08204, 2022.
[3] A. Carbonero, P. Hompe, B. Moore, and S. Spirkl. Digraphs with all induced directed cycles of the same length are not $\bar{\chi}$-bounded. arXiv:2203.15575, 2022.

[4] Blanche Descartes. A three colour problem. *Eureka*, 9(21):24-25, 1947.

[5] A. Gyárfás. On Ramsey covering-numbers. In *Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday)*, pages 801-816. Colloq. Math. Soc. Janos Bolyai 10, North-Holland, Amsterdam, 1975.

[6] V. Neumann-Lara. The dichromatic number of a digraph. *Journal of Combinatorial Theory, Series B*, 33(3):265-270, 1982.

[7] A. Scott and P. Seymour. A survey of $\chi$-boundedness. *Journal of Graph Theory*, 95(3), 2020.

[8] D. P. Sumner. Subtrees of a graph and chromatic number. In *The Theory and Applications of Graphs*, (G. Chartrand, ed.), pages 557-576, New York, 1981. John Wiley & Sons.

[9] A. Zykov. On some properties of linear complexes (in Russian). *Mat. Sbornik N.S.*, 24(66), 1949.