Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded

DOI10.37236/11179zbMath1503.05039arXiv2203.15575OpenAlexW4306652466MaRDI QIDQ2094868

Sophie Spirkl, Patrick Hompe, Alvaro Carbonero, Benjamin Moore

Publication date: 8 November 2022

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

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

zbMATH Keywords

digraphsclique numberdichromatic number\(t\)-chordal

Mathematics Subject Classification ID

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

Related Items (2)

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\) ⋮ A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Cites Work

• A note on odd/even cycles
• On the complexity of testing for odd holes and induced odd paths
• The dichromatic number of a digraph
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
• Chordal directed graphs are not \(\chi\)-bounded
• The Induced Disjoint Paths Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded