Digraphs with all induced directed cycles of the same length are not -bounded

DOI10.37236/11179MaRDI QIDQ2094868zbMATH OpenOpenAlexFDO

Authors Alvaro Carbonero, Patrick Hompe, Benjamin Moore, Sophie Spirkl

Publication date 8 November 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/2203.15575

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

\(t\)-chordalclique numberdichromatic numberdigraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: For $tge2$, let us call a digraph $D$ emph{t-chordal} if all induced directed cycles in $D$ have length equal to $t$. In a previous paper, we asked for which $t$ it is true that $t$-chordal graphs with bounded clique number have bounded dichromatic number. Recently, Aboulker, Bousquet, and de Verclos answered this in the negative for $t=3$, that is, they gave a construction of $3$-chordal digraphs with clique number at most $3$ and arbitrarily large dichromatic number. In this paper, we extend their result, giving for each $tge3$ a construction of digraphs with clique number at most $3$ and arbitrarily large dichromatic number, thus answering our question in the negative. On the other hand, we show that a more restricted class, digraphs with no induced directed cycle of length less than $t$, and no induced directed $t$-vertex path, have bounded dichromatic number if their clique number is bounded. We also show the following complexity result: for fixed $tge2$, the problem of determining whether a digraph is $t$-chordal is coNP-complete.

Review text

Stimulated by challenges for the dichromatic number, the authors establish that the family of graphs where each triangle-free induced subgraph has bounded chromatic number is not \(\chi\)-bounded. They also raise a number of open problems for the researchers who are interested in this topic. In fact, they ask in particular, whether the family of digraphs with every induced directed cycle of length \(t\), is \(\vec{\chi}\)-bounded for a fixed integer \(t>3\). \textit{P. Aboulker} et al. [ibid. 29, No. 2, Research Paper P2.17, 5 p. (2022; Zbl 1493.05130)] answered the authors' question in the negative for \(t = 3\). The authors in this article extend this negative answer to all \(t\) greater than or equal to 3. Even though \(t\)-chordal graphs are not \(\vec{\chi}\)-bounded the authors establish that deciding whether a digraph is \(t\)-chordal is coNP-complete.

Recommendations

• Chordal directed graphs are not \(\chi\)-bounded
• A note on coloring digraphs of large girth
• Extension of Gyárfás-Sumner conjecture to digraphs
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• χ‐bounded families of oriented graphs

Cites work

• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
• A note on odd/even cycles
• Chordal directed graphs are not \(\chi\)-bounded
• scientific article; zbMATH DE number 3687449 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• On the complexity of testing for odd holes and induced odd paths
• The dichromatic number of a digraph
• The Induced Disjoint Paths Problem

Cited in

(8)

• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
• Chordal directed graphs are not \(\chi\)-bounded
• χ‐bounded families of oriented graphs
• Heroes in orientations of chordal graphs
• Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄
• \((\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: Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded

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