Chordal directed graphs are not \(\chi\)-bounded
type: Item
instance of: scholarly article
title: Chordal directed graphs are not \(\chi\)-bounded
zbMATH Open document ID: 1493.05130
DOI: 10.37236/11050
author: Pierre Aboulker
author: Nicolas Bousquet
author: Rémi de Joannis de Verclos
published in: The Electronic Journal of Combinatorics
publication date: 2022-05-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/2202.01006
review text: Let \(D\) be a digraph without a directed cycle of length two. A partition of the vertices of \(D\) into \(k\) parts is called a \(k\)-dicoloring of \(D\) if none of the subdigraphs induced by parts has a directed cycle. The smallest integer \(k\) such that \(D\) has a \(k\)-dicoloring is called the dichromatic number of \(D\) and is denoted by \(\overset{\to}{\chi}(D)\). A class \(\mathcal{G}\) of digraphs is \(\overset{\to}{\chi}\)-bounded if there exists a function \(f\) such that \(\overset{\to}{\chi}(D) \leq f(\omega(D))\) for every \(D \in \mathcal{G}\), where \(\omega(D)\) denotes the clique number of the underlying graph of \(D\). Let \(\mathcal{C}_3\) be the class of digraphs with neither a transitive tournament on three vertices nor an induced directed cycle of the length of least four. The main result established in this paper is the following statement. For every \(k\), there exists \(D \in \mathcal{C}_3\) such that \(\overset{\to}{\chi}(D) \geq k\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 7525884
zbMATH Keywords: dicoloring
zbMATH Keywords: dichromatic number
zbMATH Keywords: chordal digraph
MaRDI profile type: Publication
OpenAlex ID: W4229027250
arXiv ID: 2202.01006
cites work: Extension of Gyárfás-Sumner conjecture to digraphs
cites work: Q4063176
cites work: The dichromatic number of a digraph
cites work: A survey of χ‐boundedness
cites work: Q3932997
description: scientific article