Pith. sign in

REVIEW 2 cited by

A directed Andr\'asfai-ErdH{o}s-S\'os theorem and chromatic profiles of oriented cycles

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2509.07760 v1 pith:KTIX75QA submitted 2025-09-09 math.CO

A directed Andr\'asfai-Erd\H{o}s-S\'os theorem and chromatic profiles of oriented cycles

classification math.CO
keywords deltachromaticprofiledirectedandrasfai-erdcyclesdetermine
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
abstract

The chromatic profile of a digraph $H$, denoted by $\delta_{\chi}^{+}(H,k)$, is the infimum $d$ such that any $H$-free digraph $D$ on $n$ vertices with minimum out-degree $\delta^{+}(D) \ge dn$ must be $k$-colorable. We determine the exact chromatic profile for several fundamental classes of digraphs. Our main result is a directed analogue of the Andr\'asfai-Erd\H{o}s-S\'os theorem, stating that $\delta_\chi^{+}(T_r, r-1)=\frac{3 r-7}{3 r-4}$, where $T_r$ is the transitive tournament on $r$ vertices. We then determine the chromatic profile for directed odd cycles, showing that $\delta^+_\chi(\overrightarrow{C}_{2\ell+1},2)=1/2$ for all $\ell\ge 1$. Finally, we resolve the profile for the three remaining orientations of the pentagon, establishing that $\delta_{\chi}^{+}(C_{5}',2)=\delta_{\chi}^{+}(C_{5}'',2)=\delta_{\chi}^{+}(C_{5}''',2)=1/3$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the chromatic profile for tripartite graphs and beyond

    math.CO 2026-04 unverdicted novelty 8.0

    For all H with χ(H)=3, δ_χ(H,2) belongs to the finite set {1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11, 1/6}, with complete structural characterization of the associated H and an extension to color-critical graphs via the new ...

  2. On the chromatic profile for tripartite graphs and beyond

    math.CO 2026-04 accept novelty 8.0

    For every graph H with χ(H)=3 the possible values of δ_χ(H,2) form the finite set {1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11, 1/6}, with complete structural classification of the realizing graphs H.