betaFeedback

WorksMathematics

Every tournament of dichromatic number 10k210 k^2 has a vertex whose out-neighborhood has dichromatic number more than kk

Abstract

The dichromatic number of a tournament is the minimum number of colors needed to color the vertices so that no directed cycle is monochromatic. Nguyen, Scott, and Seymour (2025) asked whether every tournament with dichromatic number 2k2k has a vertex whose out-neighborhood induces a subtournament of dichromatic number at least kk. We answer their question negatively by finding an example with dichromatic number Ω(k2)Ω(k^2). Furthermore, this quadratic bound is tight up to a constant factor; we show that for every integer k≥1k \geq 1, every tournament of dichromatic number Ω(k2)Ω(k^2) contains a vertex whose out-neighborhood induces a subtournament of dichromatic number more than kk. This improves the previous best bound O(k2log⁡k)\mathcal{O}(k^2\log k) due to Colinot and Newman (2026). To show this, we prove that every tournament of fractional dichromatic number cc has a dominating set of size at most 5c−15c-1. The proof uses Brouwer's fixed point theorem.

Paper details

vlnc:W_cze7ap57
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…