Orientations of cycles in digraphs of high chromatic number and high minimum out-degree

2025/03/25 by Hidde Koerts, Koerts, Hidde, Benjamin Moore +3 · 1 citation
Computer Science · Engineering · #05C20 (Primary) 05C38 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2503.20045

openalex publication_date 2025/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We characterize all orientations of cycles C for which for every fixed ε > 0 there exists a constant c ≥ 1 such that every digraph D without loops or parallel arcs with χ(D) ≥ c and minimum out-degree at least ε |V(D)| contains C as a subdigraph. This generalizes a result of Thomassen.

Cited by

• A directed Andrásfai-Erdős-Sós theorem and chromatic profiles of oriented cycles

Related

• Subdivisions of oriented cycles in digraphs with large chromatic number
• Oriented cycles in digraphs of large outdegree
• Arbitrary Orientations of Hamilton Cycles in Digraphs
• Dichromatic number of chordal graphs
• Orientations of graphs with uncountable chromatic number