Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number
In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.21895
curl -X POST /api/v1/records/arxiv/2609.21895/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.21895/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'