Chordal directed graphs are not -bounded

DOI10.37236/11050MaRDI QIDQ2138574zbMATH OpenOpenAlexFDO

Authors Pierre Aboulker, Nicolas Bousquet, Rémi de Joannis de Verclos

Publication date 12 May 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2202.01006

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chordal digraphdichromatic numberdicoloring

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

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 to the negative a question of Carbonero, Hompe, Moore, and Spirkl (and extends some of their results).

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\).

Recommendations

• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• A note on coloring digraphs of large girth
• Extension of Gyárfás-Sumner conjecture to digraphs
• Complete directed minors and chromatic number
• Two results on the digraph chromatic number

Cites work

• A survey of -boundedness
• Extension of Gyárfás-Sumner conjecture to digraphs
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• The dichromatic number of a digraph

Cited in

(11)

• Extension of Gyárfás-Sumner conjecture to digraphs
• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
• The categorical product of two 5-chromatic digraphs can be 3-chromatic
• Heroes in orientations of chordal graphs
• Complete directed minors and chromatic number
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄
• Bounding the chromatic number of dense digraphs by arc neighborhoods
• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• The dichromatic number of digraphs without induced subdigraphs
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄ (extended abstract)

This page was built for publication: Chordal directed graphs are not \(\chi\)-bounded

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138574)